solverforge_solver/phase/localsearch/
forager.rs

1//! Foragers for local search move selection
2//!
3//! Foragers collect accepted move indices during a step and select the
4//! best one to apply. Uses index-based API for zero-clone operation.
5
6use std::fmt::Debug;
7use std::marker::PhantomData;
8
9use solverforge_core::domain::PlanningSolution;
10
11use crate::heuristic::r#move::Move;
12
13/// Trait for collecting and selecting moves in local search.
14///
15/// Foragers are responsible for:
16/// - Collecting accepted move indices during move evaluation
17/// - Deciding when to quit evaluating early
18/// - Selecting the best move index to apply
19///
20/// # Type Parameters
21/// * `S` - The planning solution type
22/// * `M` - The move type (for trait bounds only, moves are never stored)
23pub trait LocalSearchForager<S, M>: Send + Debug
24where
25    S: PlanningSolution,
26    M: Move<S>,
27{
28    /// Called at the start of each step to reset state.
29    fn step_started(&mut self);
30
31    /// Adds an accepted move index to the forager.
32    ///
33    /// The index refers to a position in the MoveArena.
34    fn add_move_index(&mut self, index: usize, score: S::Score);
35
36    /// Returns true if the forager has collected enough moves and
37    /// wants to stop evaluating more.
38    fn is_quit_early(&self) -> bool;
39
40    /// Picks the best move index from those collected.
41    ///
42    /// Returns None if no moves were accepted.
43    fn pick_move_index(&mut self) -> Option<(usize, S::Score)>;
44}
45
46/// A forager that collects a limited number of accepted moves.
47///
48/// Once the limit is reached, it quits early. It picks the best
49/// move among those collected.
50pub struct AcceptedCountForager<S>
51where
52    S: PlanningSolution,
53{
54    /// Maximum number of accepted moves to collect.
55    accepted_count_limit: usize,
56    /// Collected move indices with their scores.
57    accepted_moves: Vec<(usize, S::Score)>,
58    _phantom: PhantomData<fn() -> S>,
59}
60
61impl<S> AcceptedCountForager<S>
62where
63    S: PlanningSolution,
64{
65    /// Creates a new forager with the given limit.
66    ///
67    /// # Arguments
68    /// * `accepted_count_limit` - Stop after collecting this many accepted moves
69    pub fn new(accepted_count_limit: usize) -> Self {
70        Self {
71            accepted_count_limit,
72            accepted_moves: Vec::new(),
73            _phantom: PhantomData,
74        }
75    }
76}
77
78impl<S> Clone for AcceptedCountForager<S>
79where
80    S: PlanningSolution,
81{
82    fn clone(&self) -> Self {
83        Self {
84            accepted_count_limit: self.accepted_count_limit,
85            accepted_moves: Vec::new(), // Fresh vec for clone
86            _phantom: PhantomData,
87        }
88    }
89}
90
91impl<S> Debug for AcceptedCountForager<S>
92where
93    S: PlanningSolution,
94{
95    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
96        f.debug_struct("AcceptedCountForager")
97            .field("accepted_count_limit", &self.accepted_count_limit)
98            .field("accepted_count", &self.accepted_moves.len())
99            .finish()
100    }
101}
102
103impl<S, M> LocalSearchForager<S, M> for AcceptedCountForager<S>
104where
105    S: PlanningSolution,
106    M: Move<S>,
107{
108    fn step_started(&mut self) {
109        self.accepted_moves.clear();
110    }
111
112    fn add_move_index(&mut self, index: usize, score: S::Score) {
113        self.accepted_moves.push((index, score));
114    }
115
116    fn is_quit_early(&self) -> bool {
117        self.accepted_moves.len() >= self.accepted_count_limit
118    }
119
120    fn pick_move_index(&mut self) -> Option<(usize, S::Score)> {
121        if self.accepted_moves.is_empty() {
122            return None;
123        }
124
125        // Find the best move (highest score)
126        let mut best_idx = 0;
127        let mut best_score = self.accepted_moves[0].1;
128
129        for (i, &(_, score)) in self.accepted_moves.iter().enumerate().skip(1) {
130            if score > best_score {
131                best_idx = i;
132                best_score = score;
133            }
134        }
135
136        // Return the best move index
137        Some(self.accepted_moves.swap_remove(best_idx))
138    }
139}
140
141/// A forager that picks the first accepted move.
142///
143/// This is the simplest forager - it quits after the first accepted move.
144pub struct FirstAcceptedForager<S>
145where
146    S: PlanningSolution,
147{
148    /// The first accepted move index.
149    accepted_move: Option<(usize, S::Score)>,
150    _phantom: PhantomData<fn() -> S>,
151}
152
153impl<S> Debug for FirstAcceptedForager<S>
154where
155    S: PlanningSolution,
156{
157    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
158        f.debug_struct("FirstAcceptedForager")
159            .field("has_move", &self.accepted_move.is_some())
160            .finish()
161    }
162}
163
164impl<S> FirstAcceptedForager<S>
165where
166    S: PlanningSolution,
167{
168    /// Creates a new first-accepted forager.
169    pub fn new() -> Self {
170        Self {
171            accepted_move: None,
172            _phantom: PhantomData,
173        }
174    }
175}
176
177impl<S> Clone for FirstAcceptedForager<S>
178where
179    S: PlanningSolution,
180{
181    fn clone(&self) -> Self {
182        Self {
183            accepted_move: None, // Fresh state for clone
184            _phantom: PhantomData,
185        }
186    }
187}
188
189impl<S> Default for FirstAcceptedForager<S>
190where
191    S: PlanningSolution,
192{
193    fn default() -> Self {
194        Self::new()
195    }
196}
197
198impl<S, M> LocalSearchForager<S, M> for FirstAcceptedForager<S>
199where
200    S: PlanningSolution,
201    M: Move<S>,
202{
203    fn step_started(&mut self) {
204        self.accepted_move = None;
205    }
206
207    fn add_move_index(&mut self, index: usize, score: S::Score) {
208        if self.accepted_move.is_none() {
209            self.accepted_move = Some((index, score));
210        }
211    }
212
213    fn is_quit_early(&self) -> bool {
214        self.accepted_move.is_some()
215    }
216
217    fn pick_move_index(&mut self) -> Option<(usize, S::Score)> {
218        self.accepted_move.take()
219    }
220}
221
222#[cfg(test)]
223mod tests {
224    use super::*;
225    use crate::heuristic::r#move::ChangeMove;
226    use solverforge_core::score::SimpleScore;
227
228    #[derive(Clone, Debug)]
229    struct DummySolution {
230        score: Option<SimpleScore>,
231    }
232
233    impl PlanningSolution for DummySolution {
234        type Score = SimpleScore;
235
236        fn score(&self) -> Option<Self::Score> {
237            self.score
238        }
239
240        fn set_score(&mut self, score: Option<Self::Score>) {
241            self.score = score;
242        }
243    }
244
245    type TestMove = ChangeMove<DummySolution, i32>;
246
247    #[test]
248    fn test_accepted_count_forager_collects_indices() {
249        let mut forager = AcceptedCountForager::<DummySolution>::new(3);
250        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::step_started(&mut forager);
251
252        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::add_move_index(&mut forager, 0, SimpleScore::of(-10));
253        assert!(!<AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::is_quit_early(&forager));
254
255        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::add_move_index(&mut forager, 1, SimpleScore::of(-5));
256        assert!(!<AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::is_quit_early(&forager));
257
258        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::add_move_index(&mut forager, 2, SimpleScore::of(-8));
259        assert!(<AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::is_quit_early(&forager));
260    }
261
262    #[test]
263    fn test_accepted_count_forager_picks_best_index() {
264        let mut forager = AcceptedCountForager::<DummySolution>::new(10);
265        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::step_started(&mut forager);
266
267        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::add_move_index(&mut forager, 0, SimpleScore::of(-10));
268        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::add_move_index(&mut forager, 1, SimpleScore::of(-5)); // Best
269        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::add_move_index(&mut forager, 2, SimpleScore::of(-8));
270
271        let (index, score) = <AcceptedCountForager<DummySolution> as LocalSearchForager<
272            DummySolution,
273            TestMove,
274        >>::pick_move_index(&mut forager)
275        .unwrap();
276        assert_eq!(index, 1);
277        assert_eq!(score, SimpleScore::of(-5));
278    }
279
280    #[test]
281    fn test_accepted_count_forager_empty() {
282        let mut forager = AcceptedCountForager::<DummySolution>::new(3);
283        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::step_started(&mut forager);
284
285        assert!(<AcceptedCountForager<DummySolution> as LocalSearchForager<
286            DummySolution,
287            TestMove,
288        >>::pick_move_index(&mut forager)
289        .is_none());
290    }
291
292    #[test]
293    fn test_first_accepted_forager() {
294        let mut forager = FirstAcceptedForager::<DummySolution>::new();
295        <FirstAcceptedForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::step_started(&mut forager);
296
297        assert!(!<FirstAcceptedForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::is_quit_early(&forager));
298
299        <FirstAcceptedForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::add_move_index(&mut forager, 0, SimpleScore::of(-10));
300        assert!(<FirstAcceptedForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::is_quit_early(&forager));
301
302        // Second move should be ignored
303        <FirstAcceptedForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::add_move_index(&mut forager, 1, SimpleScore::of(-5));
304
305        let (index, score) = <FirstAcceptedForager<DummySolution> as LocalSearchForager<
306            DummySolution,
307            TestMove,
308        >>::pick_move_index(&mut forager)
309        .unwrap();
310        // Should get the first one
311        assert_eq!(index, 0);
312        assert_eq!(score, SimpleScore::of(-10));
313    }
314
315    #[test]
316    fn test_forager_resets_on_step() {
317        let mut forager = AcceptedCountForager::<DummySolution>::new(3);
318
319        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::step_started(&mut forager);
320        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::add_move_index(&mut forager, 0, SimpleScore::of(-10));
321
322        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::step_started(&mut forager);
323        // After reset, should be empty
324        assert!(<AcceptedCountForager<DummySolution> as LocalSearchForager<
325            DummySolution,
326            TestMove,
327        >>::pick_move_index(&mut forager)
328        .is_none());
329    }
330}
solverforge_solver/phase/localsearch/forager.rs

solverforge_solver/phase/localsearch/
forager.rs
