solverforge_solver/heuristic/selector/
list_ruin.rs

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

solverforge_solver/heuristic/selector/
list_ruin.rs
