solverforge_solver/heuristic/selector/move_selector/
iter.rs

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

solverforge_solver/heuristic/selector/move_selector/
iter.rs
