solverforge_solver/heuristic/selector/
list_ruin.rs

1//! Public static adapter for the canonical streamed list-ruin cursor.
2
3use std::cell::RefCell;
4use std::fmt::Debug;
5use std::marker::PhantomData;
6
7use rand::rngs::SmallRng;
8use rand::{RngExt, SeedableRng};
9use smallvec::SmallVec;
10use solverforge_core::domain::PlanningSolution;
11use solverforge_scoring::Director;
12
13use crate::heuristic::r#move::ListRuinMove;
14use crate::heuristic::selector::list_kernel::{NativeRuinEmitter, RuinCursor, RuinSourcePool};
15
16use super::move_selector::{
17    CandidateId, MoveCandidateRef, MoveCursor, MoveSelector, MoveStreamContext,
18};
19
20/// Public list ruin selector. Candidate source selection is shared; the
21/// emitted move retains its established self-contained recreate behavior.
22pub struct ListRuinMoveSelector<S, V> {
23    min_ruin_count: usize,
24    max_ruin_count: usize,
25    rng: RefCell<SmallRng>,
26    entity_count: fn(&S) -> usize,
27    list_len: fn(&S, usize) -> usize,
28    list_get: fn(&S, usize, usize) -> Option<V>,
29    list_remove: fn(&mut S, usize, usize) -> V,
30    list_insert: fn(&mut S, usize, usize, V),
31    element_owner_fn: Option<fn(&S, &V) -> Option<usize>>,
32    variable_name: &'static str,
33    descriptor_index: usize,
34    moves_per_step: usize,
35    max_source_list_len: Option<usize>,
36    skip_empty_destinations: bool,
37    _phantom: PhantomData<fn() -> V>,
38}
39
40// The RefCell is touched only while opening a cursor to derive its private
41// seed; the cursor owns its RNG after that boundary.
42unsafe impl<S, V> Send for ListRuinMoveSelector<S, V> {}
43
44impl<S, V: Debug> Debug for ListRuinMoveSelector<S, V> {
45    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
46        f.debug_struct("ListRuinMoveSelector")
47            .field("min_ruin_count", &self.min_ruin_count)
48            .field("max_ruin_count", &self.max_ruin_count)
49            .field("moves_per_step", &self.moves_per_step)
50            .field("max_source_list_len", &self.max_source_list_len)
51            .field("skip_empty_destinations", &self.skip_empty_destinations)
52            .field("variable_name", &self.variable_name)
53            .field("descriptor_index", &self.descriptor_index)
54            .finish()
55    }
56}
57
58pub struct ListRuinMoveCursor<S, V>
59where
60    S: PlanningSolution,
61    V: Clone + PartialEq + Send + Sync + Debug + 'static,
62{
63    inner: RuinCursor<S, NativeRuinEmitter<S, V>>,
64}
65
66impl<S, V> ListRuinMoveCursor<S, V>
67where
68    S: PlanningSolution,
69    V: Clone + PartialEq + Send + Sync + Debug + 'static,
70{
71    fn new(inner: RuinCursor<S, NativeRuinEmitter<S, V>>) -> Self {
72        Self { inner }
73    }
74}
75
76impl<S, V> MoveCursor<S, ListRuinMove<S, V>> for ListRuinMoveCursor<S, V>
77where
78    S: PlanningSolution,
79    V: Clone + PartialEq + Send + Sync + Debug + 'static,
80{
81    fn next_candidate(&mut self) -> Option<CandidateId> {
82        self.inner.next_candidate()
83    }
84    fn candidate(&self, id: CandidateId) -> Option<MoveCandidateRef<'_, S, ListRuinMove<S, V>>> {
85        self.inner.candidate(id)
86    }
87    fn take_candidate(&mut self, id: CandidateId) -> ListRuinMove<S, V> {
88        self.inner.take_candidate(id)
89    }
90    fn next_owned_candidate(&mut self) -> Option<ListRuinMove<S, V>> {
91        self.inner.next_owned_candidate()
92    }
93    fn next_owned_candidate_matching(
94        &mut self,
95        predicate: for<'a> fn(MoveCandidateRef<'a, S, ListRuinMove<S, V>>) -> bool,
96    ) -> Option<ListRuinMove<S, V>> {
97        self.inner.next_owned_candidate_matching(predicate)
98    }
99    fn release_candidate(&mut self, id: CandidateId) -> bool {
100        self.inner.release_candidate(id)
101    }
102}
103
104impl<S, V> Iterator for ListRuinMoveCursor<S, V>
105where
106    S: PlanningSolution,
107    V: Clone + PartialEq + Send + Sync + Debug + 'static,
108{
109    type Item = ListRuinMove<S, V>;
110    fn next(&mut self) -> Option<Self::Item> {
111        self.next_owned_candidate()
112    }
113}
114
115impl<S, V> ListRuinMoveSelector<S, V> {
116    #[allow(clippy::too_many_arguments)]
117    pub fn new(
118        min_ruin_count: usize,
119        max_ruin_count: usize,
120        entity_count: fn(&S) -> usize,
121        list_len: fn(&S, usize) -> usize,
122        list_get: fn(&S, usize, usize) -> Option<V>,
123        list_remove: fn(&mut S, usize, usize) -> V,
124        list_insert: fn(&mut S, usize, usize, V),
125        variable_name: &'static str,
126        descriptor_index: usize,
127    ) -> Self {
128        assert!(min_ruin_count >= 1, "min_ruin_count must be at least 1");
129        assert!(
130            max_ruin_count >= min_ruin_count,
131            "max_ruin_count must be >= min_ruin_count"
132        );
133        Self {
134            min_ruin_count,
135            max_ruin_count,
136            rng: RefCell::new(SmallRng::from_rng(&mut rand::rng())),
137            entity_count,
138            list_len,
139            list_get,
140            list_remove,
141            list_insert,
142            element_owner_fn: None,
143            variable_name,
144            descriptor_index,
145            moves_per_step: 10,
146            max_source_list_len: None,
147            skip_empty_destinations: false,
148            _phantom: PhantomData,
149        }
150    }
151
152    pub fn with_moves_per_step(mut self, count: usize) -> Self {
153        self.moves_per_step = count;
154        self
155    }
156    pub fn with_max_source_list_len(mut self, max_source_list_len: Option<usize>) -> Self {
157        self.max_source_list_len = max_source_list_len;
158        self
159    }
160    pub fn with_skip_empty_destinations(mut self, skip_empty_destinations: bool) -> Self {
161        self.skip_empty_destinations = skip_empty_destinations;
162        self
163    }
164    pub fn with_seed(mut self, seed: u64) -> Self {
165        self.rng = RefCell::new(SmallRng::seed_from_u64(seed));
166        self
167    }
168    pub fn with_element_owner_fn(
169        mut self,
170        element_owner_fn: Option<fn(&S, &V) -> Option<usize>>,
171    ) -> Self {
172        self.element_owner_fn = element_owner_fn;
173        self
174    }
175}
176
177impl<S, V> MoveSelector<S, ListRuinMove<S, V>> for ListRuinMoveSelector<S, V>
178where
179    S: PlanningSolution,
180    V: Clone + PartialEq + Send + Sync + Debug + 'static,
181{
182    type Cursor<'a>
183        = ListRuinMoveCursor<S, V>
184    where
185        Self: 'a;
186
187    fn open_cursor<'a, D: Director<S>>(&'a self, score_director: &D) -> Self::Cursor<'a> {
188        self.open_cursor_with_context(score_director, MoveStreamContext::default())
189    }
190
191    fn open_cursor_with_context<'a, D: Director<S>>(
192        &'a self,
193        score_director: &D,
194        context: MoveStreamContext,
195    ) -> Self::Cursor<'a> {
196        let solution = score_director.working_solution();
197        let entity_count = (self.entity_count)(solution);
198        let non_empty = (0..entity_count)
199            .filter_map(|entity| {
200                let len = (self.list_len)(solution, entity);
201                (len > 0
202                    && self
203                        .max_source_list_len
204                        .is_none_or(|max_len| len <= max_len))
205                .then_some((entity, len))
206            })
207            .collect::<Vec<_>>();
208        let source_pool = if let Some(owner_fn) = self.element_owner_fn {
209            let eligible = non_empty
210                .iter()
211                .filter_map(|&(entity, len)| {
212                    let mut positions = SmallVec::new();
213                    for position in 0..len {
214                        let Some(element) = (self.list_get)(solution, entity, position) else {
215                            continue;
216                        };
217                        if crate::list_placement::candidate_entity_indices(
218                            Some(owner_fn),
219                            solution,
220                            entity_count,
221                            &element,
222                        )
223                        .next()
224                        .is_some()
225                        {
226                            positions.push(position);
227                        }
228                    }
229                    (!positions.is_empty()).then_some((entity, positions))
230                })
231                .collect();
232            RuinSourcePool::OwnerRestricted(eligible)
233        } else {
234            RuinSourcePool::Unrestricted(non_empty)
235        };
236        let seed = self.rng.borrow_mut().random::<u64>()
237            ^ context.offset_seed(0x7157_8011_C0DE_0001) as u64;
238        ListRuinMoveCursor::new(RuinCursor::new(
239            NativeRuinEmitter::new(
240                self.entity_count,
241                self.list_len,
242                self.list_get,
243                self.list_remove,
244                self.list_insert,
245                self.element_owner_fn,
246                self.skip_empty_destinations,
247                self.variable_name,
248                self.descriptor_index,
249            ),
250            SmallRng::seed_from_u64(seed),
251            source_pool,
252            self.moves_per_step,
253            self.min_ruin_count,
254            self.max_ruin_count,
255        ))
256    }
257
258    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
259        if (self.entity_count)(score_director.working_solution()) > 0 {
260            self.moves_per_step
261        } else {
262            0
263        }
264    }
265
266    fn is_never_ending(&self) -> bool {
267        false
268    }
269}
solverforge_solver/heuristic/selector/list_ruin.rs

solverforge_solver/heuristic/selector/
list_ruin.rs
