solverforge_solver/heuristic/selector/move_selector/
iter.rs

1pub struct MoveSelectorIter<S, M, C>
2where
3    S: PlanningSolution,
4    M: Move<S>,
5    C: MoveCursor<S, M>,
6{
7    cursor: C,
8    _phantom: PhantomData<(fn() -> S, fn() -> M)>,
9}
10
11#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
12pub struct MoveStreamContext {
13    step_index: u64,
14    step_seed: u64,
15    accepted_count_limit: Option<usize>,
16}
17
18impl MoveStreamContext {
19    pub const fn new(
20        step_index: u64,
21        step_seed: u64,
22        accepted_count_limit: Option<usize>,
23    ) -> Self {
24        Self {
25            step_index,
26            step_seed,
27            accepted_count_limit,
28        }
29    }
30
31    pub const fn step_index(self) -> u64 {
32        self.step_index
33    }
34
35    pub const fn step_seed(self) -> u64 {
36        self.step_seed
37    }
38
39    pub const fn accepted_count_limit(self) -> Option<usize> {
40        self.accepted_count_limit
41    }
42
43    pub fn start_offset(self, len: usize, salt: u64) -> usize {
44        if len <= 1 {
45            return 0;
46        }
47        if self.is_canonical() {
48            return 0;
49        }
50        (self.mixed_seed(salt) as usize) % len
51    }
52
53    pub fn stride(self, len: usize, salt: u64) -> usize {
54        if len <= 1 {
55            return 1;
56        }
57        if self.is_canonical() {
58            return 1;
59        }
60        let mut stride = (self.mixed_seed(salt) as usize % (len - 1)) + 1;
61        while gcd(stride, len) != 1 {
62            stride = if stride == len - 1 { 1 } else { stride + 1 };
63        }
64        stride
65    }
66
67    pub fn offset_seed(self, salt: u64) -> usize {
68        if self.is_canonical() {
69            return 0;
70        }
71        self.mixed_seed(salt) as usize
72    }
73
74    fn is_canonical(self) -> bool {
75        self.step_index == 0 && self.step_seed == 0 && self.accepted_count_limit.is_none()
76    }
77
78    fn mixed_seed(self, salt: u64) -> u64 {
79        splitmix64(self.step_seed ^ self.step_index.wrapping_mul(0x9E37_79B9_7F4A_7C15) ^ salt)
80    }
81}
82
83fn splitmix64(mut value: u64) -> u64 {
84    value = value.wrapping_add(0x9E37_79B9_7F4A_7C15);
85    value = (value ^ (value >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
86    value = (value ^ (value >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
87    value ^ (value >> 31)
88}
89
90fn gcd(mut left: usize, mut right: usize) -> usize {
91    while right != 0 {
92        let remainder = left % right;
93        left = right;
94        right = remainder;
95    }
96    left
97}
98
99impl<S, M, C> MoveSelectorIter<S, M, C>
100where
101    S: PlanningSolution,
102    M: Move<S>,
103    C: MoveCursor<S, M>,
104{
105    fn new(cursor: C) -> Self {
106        Self {
107            cursor,
108            _phantom: PhantomData,
109        }
110    }
111}
112
113impl<S, M, C> Iterator for MoveSelectorIter<S, M, C>
114where
115    S: PlanningSolution,
116    M: Move<S>,
117    C: MoveCursor<S, M>,
118{
119    type Item = M;
120
121    fn next(&mut self) -> Option<Self::Item> {
122        let id = self.cursor.next_candidate()?;
123        Some(self.cursor.take_candidate(id))
124    }
125}
126
127/// A zero-erasure move selector that yields stable candidate indices plus borrowable
128/// move views. Ownership is transferred only via `take_candidate`.
129pub trait MoveSelector<S: PlanningSolution, M: Move<S>>: Send + Debug {
130    type Cursor<'a>: MoveCursor<S, M> + 'a
131    where
132        Self: 'a;
133
134    fn open_cursor<'a, D: Director<S>>(&'a self, score_director: &D) -> Self::Cursor<'a>;
135
136    fn open_cursor_with_context<'a, D: Director<S>>(
137        &'a self,
138        score_director: &D,
139        _context: MoveStreamContext,
140    ) -> Self::Cursor<'a> {
141        self.open_cursor(score_director)
142    }
143
144    fn iter_moves<'a, D: Director<S>>(
145        &'a self,
146        score_director: &D,
147    ) -> MoveSelectorIter<S, M, Self::Cursor<'a>> {
148        MoveSelectorIter::new(self.open_cursor(score_director))
149    }
150
151    fn size<D: Director<S>>(&self, score_director: &D) -> usize;
152
153    fn append_moves<D: Director<S>>(&self, score_director: &D, arena: &mut MoveArena<M>) {
154        let mut cursor = self.open_cursor(score_director);
155        for id in collect_cursor_indices::<S, M, _>(&mut cursor) {
156            arena.push(cursor.take_candidate(id));
157        }
158    }
159
160    fn is_never_ending(&self) -> bool {
161        false
162    }
163}
solverforge_solver/heuristic/selector/move_selector/iter.rs

solverforge_solver/heuristic/selector/move_selector/
iter.rs
