solverforge_solver/heuristic/selector/move_selector/
iter.rs

1use solverforge_config::SelectionOrder;
2
3pub struct MoveSelectorIter<S, M, C>
4where
5    S: PlanningSolution,
6    M: Move<S>,
7    C: MoveCursor<S, M>,
8{
9    cursor: C,
10    _phantom: PhantomData<(fn() -> S, fn() -> M)>,
11}
12
13#[derive(Clone, Copy, Debug, PartialEq, Eq)]
14pub struct MoveStreamContext {
15    step_index: u64,
16    step_seed: u64,
17    accepted_count_limit: Option<usize>,
18    selection_order: SelectionOrder,
19}
20
21impl MoveStreamContext {
22    pub const fn new(
23        step_index: u64,
24        step_seed: u64,
25        accepted_count_limit: Option<usize>,
26    ) -> Self {
27        Self {
28            step_index,
29            step_seed,
30            accepted_count_limit,
31            selection_order: SelectionOrder::Original,
32        }
33    }
34
35    pub const fn with_selection_order(mut self, selection_order: SelectionOrder) -> Self {
36        self.selection_order = selection_order;
37        self
38    }
39
40    pub const fn selection_order(self) -> SelectionOrder {
41        self.selection_order
42    }
43
44    pub const fn step_index(self) -> u64 {
45        self.step_index
46    }
47
48    pub const fn step_seed(self) -> u64 {
49        self.step_seed
50    }
51
52    pub const fn accepted_count_limit(self) -> Option<usize> {
53        self.accepted_count_limit
54    }
55
56    pub fn start_offset(self, len: usize, salt: u64) -> usize {
57        if len <= 1 {
58            return 0;
59        }
60        if self.is_canonical() {
61            return 0;
62        }
63        (self.mixed_seed(salt) as usize) % len
64    }
65
66    pub fn stride(self, len: usize, salt: u64) -> usize {
67        if len <= 1 {
68            return 1;
69        }
70        if self.is_canonical() {
71            return 1;
72        }
73        let mut stride = (self.mixed_seed(salt) as usize % (len - 1)) + 1;
74        while gcd(stride, len) != 1 {
75            stride = if stride == len - 1 { 1 } else { stride + 1 };
76        }
77        stride
78    }
79
80    pub fn offset_seed(self, salt: u64) -> usize {
81        if self.is_canonical() {
82            return 0;
83        }
84        self.mixed_seed(salt) as usize
85    }
86
87    pub(crate) fn random_index(self, len: usize, salt: u64) -> usize {
88        if len <= 1 {
89            return 0;
90        }
91        (self.mixed_seed(salt) as usize) % len
92    }
93
94    pub(crate) fn random_stride(self, len: usize, salt: u64) -> usize {
95        if len <= 1 {
96            return 1;
97        }
98        let mut stride = (self.mixed_seed(salt) as usize % (len - 1)) + 1;
99        while gcd(stride, len) != 1 {
100            stride = if stride == len - 1 { 1 } else { stride + 1 };
101        }
102        stride
103    }
104
105    pub(crate) fn random_seed(self, salt: u64) -> u64 {
106        self.mixed_seed(salt)
107    }
108
109    pub(crate) fn selection_index(self, offset: usize, len: usize, salt: u64) -> usize {
110        debug_assert!(offset < len);
111        match self.selection_order {
112            SelectionOrder::Original | SelectionOrder::Sorted | SelectionOrder::Probabilistic => {
113                offset
114            }
115            SelectionOrder::Random => self.random_index(
116                len,
117                salt ^ (offset as u64).wrapping_mul(0xD1B5_4A32_D192_ED03),
118            ),
119            SelectionOrder::Shuffled => {
120                let start = self.random_index(len, salt);
121                let stride = self.random_stride(len, salt ^ 0xA24B_AED4_963E_E407);
122                (start + offset * stride) % len
123            }
124        }
125    }
126
127    /// Orders an outer source dimension without revisiting an expensive row.
128    /// `Random` remains with-replacement at the candidate coordinate level,
129    /// while source rows are traversed once in a seeded permutation.
130    pub(crate) fn selection_index_without_replacement(
131        self,
132        offset: usize,
133        len: usize,
134        salt: u64,
135    ) -> usize {
136        debug_assert!(offset < len);
137        match self.selection_order {
138            SelectionOrder::Original | SelectionOrder::Sorted | SelectionOrder::Probabilistic => {
139                offset
140            }
141            SelectionOrder::Random | SelectionOrder::Shuffled => {
142                let start = self.random_index(len, salt);
143                let stride = self.random_stride(len, salt ^ 0xA24B_AED4_963E_E407);
144                (start + offset * stride) % len
145            }
146        }
147    }
148
149    pub(crate) fn apply_selection_order<T: Clone>(self, values: &mut [T], salt: u64) {
150        if self.is_canonical() {
151            return;
152        }
153        let canonical = values.to_vec();
154        for (offset, value) in values.iter_mut().enumerate() {
155            *value = canonical[self.selection_index(offset, canonical.len(), salt)].clone();
156        }
157    }
158
159    pub(crate) fn apply_selection_order_without_replacement<T: Clone>(
160        self,
161        values: &mut [T],
162        salt: u64,
163    ) {
164        if self.is_canonical() {
165            return;
166        }
167        let canonical = values.to_vec();
168        for (offset, value) in values.iter_mut().enumerate() {
169            *value = canonical
170                [self.selection_index_without_replacement(offset, canonical.len(), salt)]
171                .clone();
172        }
173    }
174
175    pub(crate) const fn is_canonical(self) -> bool {
176        matches!(
177            self.selection_order,
178            SelectionOrder::Original | SelectionOrder::Sorted | SelectionOrder::Probabilistic
179        )
180    }
181
182    fn mixed_seed(self, salt: u64) -> u64 {
183        splitmix64(self.step_seed ^ self.step_index.wrapping_mul(0x9E37_79B9_7F4A_7C15) ^ salt)
184    }
185}
186
187impl Default for MoveStreamContext {
188    fn default() -> Self {
189        Self::new(0, 0, None)
190    }
191}
192
193fn splitmix64(mut value: u64) -> u64 {
194    value = value.wrapping_add(0x9E37_79B9_7F4A_7C15);
195    value = (value ^ (value >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
196    value = (value ^ (value >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
197    value ^ (value >> 31)
198}
199
200fn gcd(mut left: usize, mut right: usize) -> usize {
201    while right != 0 {
202        let remainder = left % right;
203        left = right;
204        right = remainder;
205    }
206    left
207}
208
209impl<S, M, C> MoveSelectorIter<S, M, C>
210where
211    S: PlanningSolution,
212    M: Move<S>,
213    C: MoveCursor<S, M>,
214{
215    fn new(cursor: C) -> Self {
216        Self {
217            cursor,
218            _phantom: PhantomData,
219        }
220    }
221}
222
223impl<S, M, C> Iterator for MoveSelectorIter<S, M, C>
224where
225    S: PlanningSolution,
226    M: Move<S>,
227    C: MoveCursor<S, M>,
228{
229    type Item = M;
230
231    #[inline(always)]
232    fn next(&mut self) -> Option<Self::Item> {
233        self.cursor.next_owned_candidate()
234    }
235}
236
237/// A zero-erasure move selector that yields stable candidate indices plus borrowable
238/// move views. Ownership is transferred only via `take_candidate`.
239pub trait MoveSelector<S: PlanningSolution, M: Move<S>>: Send + Debug {
240    type Cursor<'a>: MoveCursor<S, M> + 'a
241    where
242        Self: 'a;
243
244    fn open_cursor<'a, D: Director<S>>(&'a self, score_director: &D) -> Self::Cursor<'a>;
245
246    fn open_cursor_with_context<'a, D: Director<S>>(
247        &'a self,
248        score_director: &D,
249        _context: MoveStreamContext,
250    ) -> Self::Cursor<'a> {
251        self.open_cursor(score_director)
252    }
253
254    /// Validates director-dependent selector configuration without producing candidates.
255    ///
256    /// Composite selectors call this before deferring a child cursor so deterministic
257    /// configuration errors retain their cursor-open timing.
258    fn validate_cursor<D: Director<S>>(&self, _score_director: &D) {}
259
260    fn iter_moves<'a, D: Director<S>>(
261        &'a self,
262        score_director: &D,
263    ) -> MoveSelectorIter<S, M, Self::Cursor<'a>> {
264        MoveSelectorIter::new(self.open_cursor(score_director))
265    }
266
267    fn size<D: Director<S>>(&self, score_director: &D) -> usize;
268
269    fn append_moves<D: Director<S>>(&self, score_director: &D, arena: &mut MoveArena<M>) {
270        let mut cursor = self.open_cursor(score_director);
271        for id in collect_cursor_indices::<S, M, _>(&mut cursor) {
272            arena.push(cursor.take_candidate(id));
273        }
274    }
275
276    fn is_never_ending(&self) -> bool {
277        false
278    }
279}
solverforge_solver/heuristic/selector/move_selector/iter.rs

solverforge_solver/heuristic/selector/move_selector/
iter.rs
