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;
10use solverforge_core::score::Score;
11
12use crate::heuristic::r#move::Move;
13
14/// Trait for collecting and selecting moves in local search.
15///
16/// Foragers are responsible for:
17/// - Collecting accepted move indices during move evaluation
18/// - Deciding when to quit evaluating early
19/// - Selecting the best move index to apply
20///
21/// # Type Parameters
22/// * `S` - The planning solution type
23/// * `M` - The move type (for trait bounds only, moves are never stored)
24pub trait LocalSearchForager<S, M>: Send + Debug
25where
26    S: PlanningSolution,
27    M: Move<S>,
28{
29    /// Called at the start of each step to reset state.
30    ///
31    /// `best_score` is the best solution score ever seen.
32    /// `last_step_score` is the score at the end of the previous step.
33    /// Foragers that implement pick-early-on-improvement use these to decide
34    /// when to stop evaluating moves.
35    fn step_started(&mut self, best_score: S::Score, last_step_score: S::Score);
36
37    /// Adds an accepted move index to the forager.
38    ///
39    /// The index refers to a position in the MoveArena.
40    fn add_move_index(&mut self, index: usize, score: S::Score);
41
42    /// Returns true if the forager has collected enough moves and
43    /// wants to stop evaluating more.
44    fn is_quit_early(&self) -> bool;
45
46    /// Picks the best move index from those collected.
47    ///
48    /// Returns None if no moves were accepted.
49    fn pick_move_index(&mut self) -> Option<(usize, S::Score)>;
50}
51
52/// A forager that collects a limited number of accepted moves.
53///
54/// Once the limit is reached, it quits early. It picks the best
55/// move among those collected.
56pub struct AcceptedCountForager<S>
57where
58    S: PlanningSolution,
59{
60    /// Maximum number of accepted moves to collect.
61    accepted_count_limit: usize,
62    /// Collected move indices with their scores.
63    accepted_moves: Vec<(usize, S::Score)>,
64    _phantom: PhantomData<fn() -> S>,
65}
66
67impl<S> AcceptedCountForager<S>
68where
69    S: PlanningSolution,
70{
71    /// Creates a new forager with the given limit.
72    ///
73    /// # Panics
74    /// Panics if `accepted_count_limit` is 0 — a zero limit would quit before
75    /// evaluating any move, silently skipping every step.
76    ///
77    /// # Arguments
78    /// * `accepted_count_limit` - Stop after collecting this many accepted moves
79    pub fn new(accepted_count_limit: usize) -> Self {
80        assert!(
81            accepted_count_limit > 0,
82            "AcceptedCountForager: accepted_count_limit must be > 0, got 0"
83        );
84        Self {
85            accepted_count_limit,
86            accepted_moves: Vec::new(),
87            _phantom: PhantomData,
88        }
89    }
90}
91
92impl<S> Clone for AcceptedCountForager<S>
93where
94    S: PlanningSolution,
95{
96    fn clone(&self) -> Self {
97        Self {
98            accepted_count_limit: self.accepted_count_limit,
99            accepted_moves: Vec::new(), // Fresh vec for clone
100            _phantom: PhantomData,
101        }
102    }
103}
104
105impl<S> Debug for AcceptedCountForager<S>
106where
107    S: PlanningSolution,
108{
109    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
110        f.debug_struct("AcceptedCountForager")
111            .field("accepted_count_limit", &self.accepted_count_limit)
112            .field("accepted_count", &self.accepted_moves.len())
113            .finish()
114    }
115}
116
117impl<S, M> LocalSearchForager<S, M> for AcceptedCountForager<S>
118where
119    S: PlanningSolution,
120    M: Move<S>,
121{
122    fn step_started(&mut self, _best_score: S::Score, _last_step_score: S::Score) {
123        self.accepted_moves.clear();
124    }
125
126    fn add_move_index(&mut self, index: usize, score: S::Score) {
127        self.accepted_moves.push((index, score));
128    }
129
130    fn is_quit_early(&self) -> bool {
131        self.accepted_moves.len() >= self.accepted_count_limit
132    }
133
134    fn pick_move_index(&mut self) -> Option<(usize, S::Score)> {
135        if self.accepted_moves.is_empty() {
136            return None;
137        }
138
139        // Find the best move (highest score)
140        let mut best_idx = 0;
141        let mut best_score = self.accepted_moves[0].1;
142
143        for (i, &(_, score)) in self.accepted_moves.iter().enumerate().skip(1) {
144            if score > best_score {
145                best_idx = i;
146                best_score = score;
147            }
148        }
149
150        // Return the best move index
151        Some(self.accepted_moves.swap_remove(best_idx))
152    }
153}
154
155/// A forager that picks the first accepted move.
156///
157/// This is the simplest forager - it quits after the first accepted move.
158pub struct FirstAcceptedForager<S>
159where
160    S: PlanningSolution,
161{
162    /// The first accepted move index.
163    accepted_move: Option<(usize, S::Score)>,
164    _phantom: PhantomData<fn() -> S>,
165}
166
167impl<S> Debug for FirstAcceptedForager<S>
168where
169    S: PlanningSolution,
170{
171    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
172        f.debug_struct("FirstAcceptedForager")
173            .field("has_move", &self.accepted_move.is_some())
174            .finish()
175    }
176}
177
178impl<S> FirstAcceptedForager<S>
179where
180    S: PlanningSolution,
181{
182    /// Creates a new first-accepted forager.
183    pub fn new() -> Self {
184        Self {
185            accepted_move: None,
186            _phantom: PhantomData,
187        }
188    }
189}
190
191impl<S> Clone for FirstAcceptedForager<S>
192where
193    S: PlanningSolution,
194{
195    fn clone(&self) -> Self {
196        Self {
197            accepted_move: None, // Fresh state for clone
198            _phantom: PhantomData,
199        }
200    }
201}
202
203impl<S> Default for FirstAcceptedForager<S>
204where
205    S: PlanningSolution,
206{
207    fn default() -> Self {
208        Self::new()
209    }
210}
211
212impl<S, M> LocalSearchForager<S, M> for FirstAcceptedForager<S>
213where
214    S: PlanningSolution,
215    M: Move<S>,
216{
217    fn step_started(&mut self, _best_score: S::Score, _last_step_score: S::Score) {
218        self.accepted_move = None;
219    }
220
221    fn add_move_index(&mut self, index: usize, score: S::Score) {
222        if self.accepted_move.is_none() {
223            self.accepted_move = Some((index, score));
224        }
225    }
226
227    fn is_quit_early(&self) -> bool {
228        self.accepted_move.is_some()
229    }
230
231    fn pick_move_index(&mut self) -> Option<(usize, S::Score)> {
232        self.accepted_move.take()
233    }
234}
235
236/// A forager that evaluates all accepted moves and picks the best.
237///
238/// Unlike `AcceptedCountForager(N)`, this forager never quits early — it
239/// always evaluates the full move space before selecting the best score.
240pub struct BestScoreForager<S>
241where
242    S: PlanningSolution,
243{
244    /// Collected move indices with their scores.
245    accepted_moves: Vec<(usize, S::Score)>,
246    _phantom: PhantomData<fn() -> S>,
247}
248
249impl<S> BestScoreForager<S>
250where
251    S: PlanningSolution,
252{
253    /// Creates a new best-score forager.
254    pub fn new() -> Self {
255        Self {
256            accepted_moves: Vec::new(),
257            _phantom: PhantomData,
258        }
259    }
260}
261
262impl<S> Default for BestScoreForager<S>
263where
264    S: PlanningSolution,
265{
266    fn default() -> Self {
267        Self::new()
268    }
269}
270
271impl<S> Debug for BestScoreForager<S>
272where
273    S: PlanningSolution,
274{
275    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
276        f.debug_struct("BestScoreForager")
277            .field("accepted_count", &self.accepted_moves.len())
278            .finish()
279    }
280}
281
282impl<S> Clone for BestScoreForager<S>
283where
284    S: PlanningSolution,
285{
286    fn clone(&self) -> Self {
287        Self {
288            accepted_moves: Vec::new(),
289            _phantom: PhantomData,
290        }
291    }
292}
293
294impl<S, M> LocalSearchForager<S, M> for BestScoreForager<S>
295where
296    S: PlanningSolution,
297    M: Move<S>,
298{
299    fn step_started(&mut self, _best_score: S::Score, _last_step_score: S::Score) {
300        self.accepted_moves.clear();
301    }
302
303    fn add_move_index(&mut self, index: usize, score: S::Score) {
304        self.accepted_moves.push((index, score));
305    }
306
307    fn is_quit_early(&self) -> bool {
308        false // Never quit early — always evaluate the full move space
309    }
310
311    fn pick_move_index(&mut self) -> Option<(usize, S::Score)> {
312        if self.accepted_moves.is_empty() {
313            return None;
314        }
315        let mut best_idx = 0;
316        let mut best_score = self.accepted_moves[0].1;
317        for (i, &(_, score)) in self.accepted_moves.iter().enumerate().skip(1) {
318            if score > best_score {
319                best_idx = i;
320                best_score = score;
321            }
322        }
323        Some(self.accepted_moves.swap_remove(best_idx))
324    }
325}
326
327/// A forager that picks the first accepted move that improves on the best score ever seen.
328///
329/// Once a move with a score strictly better than the all-time best is found, the
330/// forager quits immediately and selects that move. If no such move exists, it falls
331/// back to the best among all accepted moves.
332pub struct FirstBestScoreImprovingForager<S>
333where
334    S: PlanningSolution,
335{
336    /// All-time best score — set at the start of each step.
337    best_score: S::Score,
338    /// Collected move indices with their scores.
339    accepted_moves: Vec<(usize, S::Score)>,
340    /// Whether we found a move that beats the best score.
341    found_best_improving: bool,
342    _phantom: PhantomData<fn() -> S>,
343}
344
345impl<S> FirstBestScoreImprovingForager<S>
346where
347    S: PlanningSolution,
348{
349    /// Creates a new first-best-score-improving forager.
350    pub fn new() -> Self {
351        Self {
352            best_score: S::Score::zero(),
353            accepted_moves: Vec::new(),
354            found_best_improving: false,
355            _phantom: PhantomData,
356        }
357    }
358}
359
360impl<S> Default for FirstBestScoreImprovingForager<S>
361where
362    S: PlanningSolution,
363{
364    fn default() -> Self {
365        Self::new()
366    }
367}
368
369impl<S> Debug for FirstBestScoreImprovingForager<S>
370where
371    S: PlanningSolution,
372{
373    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
374        f.debug_struct("FirstBestScoreImprovingForager")
375            .field("found_best_improving", &self.found_best_improving)
376            .finish()
377    }
378}
379
380impl<S> Clone for FirstBestScoreImprovingForager<S>
381where
382    S: PlanningSolution,
383{
384    fn clone(&self) -> Self {
385        Self {
386            best_score: self.best_score,
387            accepted_moves: Vec::new(),
388            found_best_improving: false,
389            _phantom: PhantomData,
390        }
391    }
392}
393
394impl<S, M> LocalSearchForager<S, M> for FirstBestScoreImprovingForager<S>
395where
396    S: PlanningSolution,
397    M: Move<S>,
398{
399    fn step_started(&mut self, best_score: S::Score, _last_step_score: S::Score) {
400        self.best_score = best_score;
401        self.accepted_moves.clear();
402        self.found_best_improving = false;
403    }
404
405    fn add_move_index(&mut self, index: usize, score: S::Score) {
406        if score > self.best_score {
407            // Found a best-improving move — keep only this one and quit early
408            self.accepted_moves.clear();
409            self.accepted_moves.push((index, score));
410            self.found_best_improving = true;
411        } else {
412            // Track as fallback unless already found best-improving
413            if !self.found_best_improving {
414                self.accepted_moves.push((index, score));
415            }
416        }
417    }
418
419    fn is_quit_early(&self) -> bool {
420        self.found_best_improving
421    }
422
423    fn pick_move_index(&mut self) -> Option<(usize, S::Score)> {
424        if self.accepted_moves.is_empty() {
425            return None;
426        }
427        // If we found a best-improving move it's always the single entry (already best)
428        if self.found_best_improving {
429            return self.accepted_moves.pop();
430        }
431        // Otherwise pick the best among all collected fallbacks
432        let mut best_idx = 0;
433        let mut best_score = self.accepted_moves[0].1;
434        for (i, &(_, score)) in self.accepted_moves.iter().enumerate().skip(1) {
435            if score > best_score {
436                best_idx = i;
437                best_score = score;
438            }
439        }
440        Some(self.accepted_moves.swap_remove(best_idx))
441    }
442}
443
444/// A forager that picks the first accepted move that improves on the last step's score.
445///
446/// Once a move with a score strictly better than the previous step is found, the
447/// forager quits immediately and selects that move. If no such move exists, it falls
448/// back to the best among all accepted moves.
449pub struct FirstLastStepScoreImprovingForager<S>
450where
451    S: PlanningSolution,
452{
453    /// Score at the end of the previous step — set at the start of each step.
454    last_step_score: S::Score,
455    /// Collected move indices with their scores.
456    accepted_moves: Vec<(usize, S::Score)>,
457    /// Whether we found a move that beats the last step score.
458    found_last_step_improving: bool,
459    _phantom: PhantomData<fn() -> S>,
460}
461
462impl<S> FirstLastStepScoreImprovingForager<S>
463where
464    S: PlanningSolution,
465{
466    /// Creates a new first-last-step-score-improving forager.
467    pub fn new() -> Self {
468        Self {
469            last_step_score: S::Score::zero(),
470            accepted_moves: Vec::new(),
471            found_last_step_improving: false,
472            _phantom: PhantomData,
473        }
474    }
475}
476
477impl<S> Default for FirstLastStepScoreImprovingForager<S>
478where
479    S: PlanningSolution,
480{
481    fn default() -> Self {
482        Self::new()
483    }
484}
485
486impl<S> Debug for FirstLastStepScoreImprovingForager<S>
487where
488    S: PlanningSolution,
489{
490    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
491        f.debug_struct("FirstLastStepScoreImprovingForager")
492            .field("found_last_step_improving", &self.found_last_step_improving)
493            .finish()
494    }
495}
496
497impl<S> Clone for FirstLastStepScoreImprovingForager<S>
498where
499    S: PlanningSolution,
500{
501    fn clone(&self) -> Self {
502        Self {
503            last_step_score: self.last_step_score,
504            accepted_moves: Vec::new(),
505            found_last_step_improving: false,
506            _phantom: PhantomData,
507        }
508    }
509}
510
511impl<S, M> LocalSearchForager<S, M> for FirstLastStepScoreImprovingForager<S>
512where
513    S: PlanningSolution,
514    M: Move<S>,
515{
516    fn step_started(&mut self, _best_score: S::Score, last_step_score: S::Score) {
517        self.last_step_score = last_step_score;
518        self.accepted_moves.clear();
519        self.found_last_step_improving = false;
520    }
521
522    fn add_move_index(&mut self, index: usize, score: S::Score) {
523        if score > self.last_step_score {
524            // Found a last-step-improving move — keep only this one and quit early
525            self.accepted_moves.clear();
526            self.accepted_moves.push((index, score));
527            self.found_last_step_improving = true;
528        } else if !self.found_last_step_improving {
529            self.accepted_moves.push((index, score));
530        }
531    }
532
533    fn is_quit_early(&self) -> bool {
534        self.found_last_step_improving
535    }
536
537    fn pick_move_index(&mut self) -> Option<(usize, S::Score)> {
538        if self.accepted_moves.is_empty() {
539            return None;
540        }
541        if self.found_last_step_improving {
542            return self.accepted_moves.pop();
543        }
544        let mut best_idx = 0;
545        let mut best_score = self.accepted_moves[0].1;
546        for (i, &(_, score)) in self.accepted_moves.iter().enumerate().skip(1) {
547            if score > best_score {
548                best_idx = i;
549                best_score = score;
550            }
551        }
552        Some(self.accepted_moves.swap_remove(best_idx))
553    }
554}
555
556#[cfg(test)]
557mod tests {
558    use super::*;
559    use crate::heuristic::r#move::ChangeMove;
560    use solverforge_core::score::SimpleScore;
561
562    #[derive(Clone, Debug)]
563    struct DummySolution {
564        score: Option<SimpleScore>,
565    }
566
567    impl PlanningSolution for DummySolution {
568        type Score = SimpleScore;
569
570        fn score(&self) -> Option<Self::Score> {
571            self.score
572        }
573
574        fn set_score(&mut self, score: Option<Self::Score>) {
575            self.score = score;
576        }
577    }
578
579    type TestMove = ChangeMove<DummySolution, i32>;
580
581    fn zero() -> SimpleScore {
582        SimpleScore::of(0)
583    }
584
585    #[test]
586    fn test_accepted_count_forager_collects_indices() {
587        let mut forager = AcceptedCountForager::<DummySolution>::new(3);
588        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::step_started(&mut forager, zero(), zero());
589
590        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::add_move_index(&mut forager, 0, SimpleScore::of(-10));
591        assert!(!<AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::is_quit_early(&forager));
592
593        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::add_move_index(&mut forager, 1, SimpleScore::of(-5));
594        assert!(!<AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::is_quit_early(&forager));
595
596        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::add_move_index(&mut forager, 2, SimpleScore::of(-8));
597        assert!(<AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::is_quit_early(&forager));
598    }
599
600    #[test]
601    fn test_accepted_count_forager_picks_best_index() {
602        let mut forager = AcceptedCountForager::<DummySolution>::new(10);
603        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::step_started(&mut forager, zero(), zero());
604
605        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::add_move_index(&mut forager, 0, SimpleScore::of(-10));
606        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::add_move_index(&mut forager, 1, SimpleScore::of(-5)); // Best
607        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::add_move_index(&mut forager, 2, SimpleScore::of(-8));
608
609        let (index, score) = <AcceptedCountForager<DummySolution> as LocalSearchForager<
610            DummySolution,
611            TestMove,
612        >>::pick_move_index(&mut forager)
613        .unwrap();
614        assert_eq!(index, 1);
615        assert_eq!(score, SimpleScore::of(-5));
616    }
617
618    #[test]
619    fn test_accepted_count_forager_empty() {
620        let mut forager = AcceptedCountForager::<DummySolution>::new(3);
621        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::step_started(&mut forager, zero(), zero());
622
623        assert!(<AcceptedCountForager<DummySolution> as LocalSearchForager<
624            DummySolution,
625            TestMove,
626        >>::pick_move_index(&mut forager)
627        .is_none());
628    }
629
630    #[test]
631    fn test_first_accepted_forager() {
632        let mut forager = FirstAcceptedForager::<DummySolution>::new();
633        <FirstAcceptedForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::step_started(&mut forager, zero(), zero());
634
635        assert!(!<FirstAcceptedForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::is_quit_early(&forager));
636
637        <FirstAcceptedForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::add_move_index(&mut forager, 0, SimpleScore::of(-10));
638        assert!(<FirstAcceptedForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::is_quit_early(&forager));
639
640        // Second move should be ignored
641        <FirstAcceptedForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::add_move_index(&mut forager, 1, SimpleScore::of(-5));
642
643        let (index, score) = <FirstAcceptedForager<DummySolution> as LocalSearchForager<
644            DummySolution,
645            TestMove,
646        >>::pick_move_index(&mut forager)
647        .unwrap();
648        // Should get the first one
649        assert_eq!(index, 0);
650        assert_eq!(score, SimpleScore::of(-10));
651    }
652
653    #[test]
654    fn test_forager_resets_on_step() {
655        let mut forager = AcceptedCountForager::<DummySolution>::new(3);
656
657        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::step_started(&mut forager, zero(), zero());
658        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::add_move_index(&mut forager, 0, SimpleScore::of(-10));
659
660        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::step_started(&mut forager, zero(), zero());
661        // After reset, should be empty
662        assert!(<AcceptedCountForager<DummySolution> as LocalSearchForager<
663            DummySolution,
664            TestMove,
665        >>::pick_move_index(&mut forager)
666        .is_none());
667    }
668
669    #[test]
670    #[should_panic(expected = "accepted_count_limit must be > 0")]
671    fn test_accepted_count_forager_zero_panics() {
672        let _ = AcceptedCountForager::<DummySolution>::new(0);
673    }
674
675    #[test]
676    fn test_best_score_forager_never_quits_early() {
677        let mut forager = BestScoreForager::<DummySolution>::new();
678        <BestScoreForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::step_started(&mut forager, zero(), zero());
679
680        <BestScoreForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::add_move_index(&mut forager, 0, SimpleScore::of(-5));
681        assert!(!<BestScoreForager<DummySolution> as LocalSearchForager<
682            DummySolution,
683            TestMove,
684        >>::is_quit_early(&forager));
685
686        <BestScoreForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::add_move_index(&mut forager, 1, SimpleScore::of(-1));
687        let (index, score) = <BestScoreForager<DummySolution> as LocalSearchForager<
688            DummySolution,
689            TestMove,
690        >>::pick_move_index(&mut forager)
691        .unwrap();
692        assert_eq!(index, 1);
693        assert_eq!(score, SimpleScore::of(-1));
694    }
695
696    #[test]
697    fn test_first_best_score_improving_quits_on_improvement() {
698        let best = SimpleScore::of(-10);
699        let mut forager = FirstBestScoreImprovingForager::<DummySolution>::new();
700        <FirstBestScoreImprovingForager<DummySolution> as LocalSearchForager<
701            DummySolution,
702            TestMove,
703        >>::step_started(&mut forager, best, zero());
704
705        // Score -15 is worse than best (-10), not improving
706        <FirstBestScoreImprovingForager<DummySolution> as LocalSearchForager<
707            DummySolution,
708            TestMove,
709        >>::add_move_index(&mut forager, 0, SimpleScore::of(-15));
710        assert!(
711            !<FirstBestScoreImprovingForager<DummySolution> as LocalSearchForager<
712                DummySolution,
713                TestMove,
714            >>::is_quit_early(&forager)
715        );
716
717        // Score -5 is better than best (-10), triggers early quit
718        <FirstBestScoreImprovingForager<DummySolution> as LocalSearchForager<
719            DummySolution,
720            TestMove,
721        >>::add_move_index(&mut forager, 1, SimpleScore::of(-5));
722        assert!(
723            <FirstBestScoreImprovingForager<DummySolution> as LocalSearchForager<
724                DummySolution,
725                TestMove,
726            >>::is_quit_early(&forager)
727        );
728
729        let (index, score) =
730            <FirstBestScoreImprovingForager<DummySolution> as LocalSearchForager<
731                DummySolution,
732                TestMove,
733            >>::pick_move_index(&mut forager)
734            .unwrap();
735        assert_eq!(index, 1);
736        assert_eq!(score, SimpleScore::of(-5));
737    }
738
739    #[test]
740    fn test_first_last_step_improving_quits_on_improvement() {
741        let last_step = SimpleScore::of(-10);
742        let mut forager = FirstLastStepScoreImprovingForager::<DummySolution>::new();
743        <FirstLastStepScoreImprovingForager<DummySolution> as LocalSearchForager<
744            DummySolution,
745            TestMove,
746        >>::step_started(&mut forager, zero(), last_step);
747
748        // Score -15 is worse than last step (-10)
749        <FirstLastStepScoreImprovingForager<DummySolution> as LocalSearchForager<
750            DummySolution,
751            TestMove,
752        >>::add_move_index(&mut forager, 0, SimpleScore::of(-15));
753        assert!(
754            !<FirstLastStepScoreImprovingForager<DummySolution> as LocalSearchForager<
755                DummySolution,
756                TestMove,
757            >>::is_quit_early(&forager)
758        );
759
760        // Score -5 is better than last step (-10), triggers early quit
761        <FirstLastStepScoreImprovingForager<DummySolution> as LocalSearchForager<
762            DummySolution,
763            TestMove,
764        >>::add_move_index(&mut forager, 1, SimpleScore::of(-5));
765        assert!(
766            <FirstLastStepScoreImprovingForager<DummySolution> as LocalSearchForager<
767                DummySolution,
768                TestMove,
769            >>::is_quit_early(&forager)
770        );
771
772        let (index, score) =
773            <FirstLastStepScoreImprovingForager<DummySolution> as LocalSearchForager<
774                DummySolution,
775                TestMove,
776            >>::pick_move_index(&mut forager)
777            .unwrap();
778        assert_eq!(index, 1);
779        assert_eq!(score, SimpleScore::of(-5));
780    }
781}
solverforge_solver/phase/localsearch/forager.rs

solverforge_solver/phase/localsearch/
forager.rs
