solverforge_solver/phase/localsearch/
forager.rs

1/* Foragers for local search move selection
2
3Foragers collect accepted move indices during a step and select the
4best one to apply. Uses index-based API for zero-clone operation.
5*/
6
7use std::fmt::Debug;
8use std::marker::PhantomData;
9
10use solverforge_core::domain::PlanningSolution;
11use solverforge_core::score::Score;
12
13use crate::heuristic::r#move::Move;
14
15/// Trait for collecting and selecting moves in local search.
16///
17/// Foragers are responsible for:
18/// - Collecting accepted move indices during move evaluation
19/// - Deciding when to quit evaluating early
20/// - Selecting the best move index to apply
21///
22/// # Type Parameters
23/// * `S` - The planning solution type
24/// * `M` - The move type (for trait bounds only, moves are never stored)
25pub trait LocalSearchForager<S, M>: Send + Debug
26where
27    S: PlanningSolution,
28    M: Move<S>,
29{
30    /* Called at the start of each step to reset state.
31
32    `best_score` is the best solution score ever seen.
33    `last_step_score` is the score at the end of the previous step.
34    Foragers that implement pick-early-on-improvement use these to decide
35    when to stop evaluating moves.
36    */
37    fn step_started(&mut self, best_score: S::Score, last_step_score: S::Score);
38
39    /* Adds an accepted move index to the forager.
40
41    The index refers to a position in the MoveArena.
42    */
43    fn add_move_index(&mut self, index: usize, score: S::Score);
44
45    // Returns true if the forager has collected enough moves and
46    // wants to stop evaluating more.
47    fn is_quit_early(&self) -> bool;
48
49    /* Picks the best move index from those collected.
50
51    Returns None if no moves were accepted.
52    */
53    fn pick_move_index(&mut self) -> Option<(usize, S::Score)>;
54}
55
56/// A forager that collects a limited number of accepted moves.
57///
58/// Once the limit is reached, it quits early. It picks the best
59/// move among those collected.
60pub struct AcceptedCountForager<S>
61where
62    S: PlanningSolution,
63{
64    // Maximum number of accepted moves to collect.
65    accepted_count_limit: usize,
66    // Collected move indices with their scores.
67    accepted_moves: Vec<(usize, S::Score)>,
68    _phantom: PhantomData<fn() -> S>,
69}
70
71impl<S> AcceptedCountForager<S>
72where
73    S: PlanningSolution,
74{
75    /// Creates a new forager with the given limit.
76    ///
77    /// # Panics
78    /// Panics if `accepted_count_limit` is 0 — a zero limit would quit before
79    /// evaluating any move, silently skipping every step.
80    ///
81    /// # Arguments
82    /// * `accepted_count_limit` - Stop after collecting this many accepted moves
83    pub fn new(accepted_count_limit: usize) -> Self {
84        assert!(
85            accepted_count_limit > 0,
86            "AcceptedCountForager: accepted_count_limit must be > 0, got 0"
87        );
88        Self {
89            accepted_count_limit,
90            accepted_moves: Vec::new(),
91            _phantom: PhantomData,
92        }
93    }
94}
95
96impl<S> Clone for AcceptedCountForager<S>
97where
98    S: PlanningSolution,
99{
100    fn clone(&self) -> Self {
101        Self {
102            accepted_count_limit: self.accepted_count_limit,
103            accepted_moves: Vec::new(), // Fresh vec for clone
104            _phantom: PhantomData,
105        }
106    }
107}
108
109impl<S> Debug for AcceptedCountForager<S>
110where
111    S: PlanningSolution,
112{
113    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
114        f.debug_struct("AcceptedCountForager")
115            .field("accepted_count_limit", &self.accepted_count_limit)
116            .field("accepted_count", &self.accepted_moves.len())
117            .finish()
118    }
119}
120
121impl<S, M> LocalSearchForager<S, M> for AcceptedCountForager<S>
122where
123    S: PlanningSolution,
124    M: Move<S>,
125{
126    fn step_started(&mut self, _best_score: S::Score, _last_step_score: S::Score) {
127        self.accepted_moves.clear();
128    }
129
130    fn add_move_index(&mut self, index: usize, score: S::Score) {
131        self.accepted_moves.push((index, score));
132    }
133
134    fn is_quit_early(&self) -> bool {
135        self.accepted_moves.len() >= self.accepted_count_limit
136    }
137
138    fn pick_move_index(&mut self) -> Option<(usize, S::Score)> {
139        if self.accepted_moves.is_empty() {
140            return None;
141        }
142
143        // Find the best move (highest score)
144        let mut best_idx = 0;
145        let mut best_score = self.accepted_moves[0].1;
146
147        for (i, &(_, score)) in self.accepted_moves.iter().enumerate().skip(1) {
148            if score > best_score {
149                best_idx = i;
150                best_score = score;
151            }
152        }
153
154        // Return the best move index
155        Some(self.accepted_moves.swap_remove(best_idx))
156    }
157}
158
159/// A forager that picks the first accepted move.
160///
161/// This is the simplest forager - it quits after the first accepted move.
162pub struct FirstAcceptedForager<S>
163where
164    S: PlanningSolution,
165{
166    // The first accepted move index.
167    accepted_move: Option<(usize, S::Score)>,
168    _phantom: PhantomData<fn() -> S>,
169}
170
171impl<S> Debug for FirstAcceptedForager<S>
172where
173    S: PlanningSolution,
174{
175    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
176        f.debug_struct("FirstAcceptedForager")
177            .field("has_move", &self.accepted_move.is_some())
178            .finish()
179    }
180}
181
182impl<S> FirstAcceptedForager<S>
183where
184    S: PlanningSolution,
185{
186    pub fn new() -> Self {
187        Self {
188            accepted_move: None,
189            _phantom: PhantomData,
190        }
191    }
192}
193
194impl<S> Clone for FirstAcceptedForager<S>
195where
196    S: PlanningSolution,
197{
198    fn clone(&self) -> Self {
199        Self {
200            accepted_move: None, // Fresh state for clone
201            _phantom: PhantomData,
202        }
203    }
204}
205
206impl<S> Default for FirstAcceptedForager<S>
207where
208    S: PlanningSolution,
209{
210    fn default() -> Self {
211        Self::new()
212    }
213}
214
215impl<S, M> LocalSearchForager<S, M> for FirstAcceptedForager<S>
216where
217    S: PlanningSolution,
218    M: Move<S>,
219{
220    fn step_started(&mut self, _best_score: S::Score, _last_step_score: S::Score) {
221        self.accepted_move = None;
222    }
223
224    fn add_move_index(&mut self, index: usize, score: S::Score) {
225        if self.accepted_move.is_none() {
226            self.accepted_move = Some((index, score));
227        }
228    }
229
230    fn is_quit_early(&self) -> bool {
231        self.accepted_move.is_some()
232    }
233
234    fn pick_move_index(&mut self) -> Option<(usize, S::Score)> {
235        self.accepted_move.take()
236    }
237}
238
239/// A forager that evaluates all accepted moves and picks the best.
240///
241/// Unlike `AcceptedCountForager(N)`, this forager never quits early — it
242/// always evaluates the full move space before selecting the best score.
243pub struct BestScoreForager<S>
244where
245    S: PlanningSolution,
246{
247    // Collected move indices with their scores.
248    accepted_moves: Vec<(usize, S::Score)>,
249    _phantom: PhantomData<fn() -> S>,
250}
251
252impl<S> BestScoreForager<S>
253where
254    S: PlanningSolution,
255{
256    pub fn new() -> Self {
257        Self {
258            accepted_moves: Vec::new(),
259            _phantom: PhantomData,
260        }
261    }
262}
263
264impl<S> Default for BestScoreForager<S>
265where
266    S: PlanningSolution,
267{
268    fn default() -> Self {
269        Self::new()
270    }
271}
272
273impl<S> Debug for BestScoreForager<S>
274where
275    S: PlanningSolution,
276{
277    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
278        f.debug_struct("BestScoreForager")
279            .field("accepted_count", &self.accepted_moves.len())
280            .finish()
281    }
282}
283
284impl<S> Clone for BestScoreForager<S>
285where
286    S: PlanningSolution,
287{
288    fn clone(&self) -> Self {
289        Self {
290            accepted_moves: Vec::new(),
291            _phantom: PhantomData,
292        }
293    }
294}
295
296impl<S, M> LocalSearchForager<S, M> for BestScoreForager<S>
297where
298    S: PlanningSolution,
299    M: Move<S>,
300{
301    fn step_started(&mut self, _best_score: S::Score, _last_step_score: S::Score) {
302        self.accepted_moves.clear();
303    }
304
305    fn add_move_index(&mut self, index: usize, score: S::Score) {
306        self.accepted_moves.push((index, score));
307    }
308
309    fn is_quit_early(&self) -> bool {
310        false // Never quit early — always evaluate the full move space
311    }
312
313    fn pick_move_index(&mut self) -> Option<(usize, S::Score)> {
314        if self.accepted_moves.is_empty() {
315            return None;
316        }
317        let mut best_idx = 0;
318        let mut best_score = self.accepted_moves[0].1;
319        for (i, &(_, score)) in self.accepted_moves.iter().enumerate().skip(1) {
320            if score > best_score {
321                best_idx = i;
322                best_score = score;
323            }
324        }
325        Some(self.accepted_moves.swap_remove(best_idx))
326    }
327}
328
329/// A forager that picks the first accepted move that improves on the best score ever seen.
330///
331/// Once a move with a score strictly better than the all-time best is found, the
332/// forager quits immediately and selects that move. If no such move exists, it falls
333/// back to the best among all accepted moves.
334pub struct FirstBestScoreImprovingForager<S>
335where
336    S: PlanningSolution,
337{
338    // All-time best score — set at the start of each step.
339    best_score: S::Score,
340    // Collected move indices with their scores.
341    accepted_moves: Vec<(usize, S::Score)>,
342    // Whether we found a move that beats the best score.
343    found_best_improving: bool,
344    _phantom: PhantomData<fn() -> S>,
345}
346
347impl<S> FirstBestScoreImprovingForager<S>
348where
349    S: PlanningSolution,
350{
351    pub fn new() -> Self {
352        Self {
353            best_score: S::Score::zero(),
354            accepted_moves: Vec::new(),
355            found_best_improving: false,
356            _phantom: PhantomData,
357        }
358    }
359}
360
361impl<S> Default for FirstBestScoreImprovingForager<S>
362where
363    S: PlanningSolution,
364{
365    fn default() -> Self {
366        Self::new()
367    }
368}
369
370impl<S> Debug for FirstBestScoreImprovingForager<S>
371where
372    S: PlanningSolution,
373{
374    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
375        f.debug_struct("FirstBestScoreImprovingForager")
376            .field("found_best_improving", &self.found_best_improving)
377            .finish()
378    }
379}
380
381impl<S> Clone for FirstBestScoreImprovingForager<S>
382where
383    S: PlanningSolution,
384{
385    fn clone(&self) -> Self {
386        Self {
387            best_score: self.best_score,
388            accepted_moves: Vec::new(),
389            found_best_improving: false,
390            _phantom: PhantomData,
391        }
392    }
393}
394
395impl<S, M> LocalSearchForager<S, M> for FirstBestScoreImprovingForager<S>
396where
397    S: PlanningSolution,
398    M: Move<S>,
399{
400    fn step_started(&mut self, best_score: S::Score, _last_step_score: S::Score) {
401        self.best_score = best_score;
402        self.accepted_moves.clear();
403        self.found_best_improving = false;
404    }
405
406    fn add_move_index(&mut self, index: usize, score: S::Score) {
407        if score > self.best_score {
408            // Found a best-improving move — keep only this one and quit early
409            self.accepted_moves.clear();
410            self.accepted_moves.push((index, score));
411            self.found_best_improving = true;
412        } else {
413            // Track as fallback unless already found best-improving
414            if !self.found_best_improving {
415                self.accepted_moves.push((index, score));
416            }
417        }
418    }
419
420    fn is_quit_early(&self) -> bool {
421        self.found_best_improving
422    }
423
424    fn pick_move_index(&mut self) -> Option<(usize, S::Score)> {
425        if self.accepted_moves.is_empty() {
426            return None;
427        }
428        // If we found a best-improving move it's always the single entry (already best)
429        if self.found_best_improving {
430            return self.accepted_moves.pop();
431        }
432        // Otherwise pick the best among all collected fallbacks
433        let mut best_idx = 0;
434        let mut best_score = self.accepted_moves[0].1;
435        for (i, &(_, score)) in self.accepted_moves.iter().enumerate().skip(1) {
436            if score > best_score {
437                best_idx = i;
438                best_score = score;
439            }
440        }
441        Some(self.accepted_moves.swap_remove(best_idx))
442    }
443}
444
445/// A forager that picks the first accepted move that improves on the last step's score.
446///
447/// Once a move with a score strictly better than the previous step is found, the
448/// forager quits immediately and selects that move. If no such move exists, it falls
449/// back to the best among all accepted moves.
450pub struct FirstLastStepScoreImprovingForager<S>
451where
452    S: PlanningSolution,
453{
454    // Score at the end of the previous step — set at the start of each step.
455    last_step_score: S::Score,
456    // Collected move indices with their scores.
457    accepted_moves: Vec<(usize, S::Score)>,
458    // Whether we found a move that beats the last step score.
459    found_last_step_improving: bool,
460    _phantom: PhantomData<fn() -> S>,
461}
462
463impl<S> FirstLastStepScoreImprovingForager<S>
464where
465    S: PlanningSolution,
466{
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::SoftScore;
561
562    #[derive(Clone, Debug)]
563    struct DummySolution {
564        score: Option<SoftScore>,
565    }
566
567    impl PlanningSolution for DummySolution {
568        type Score = SoftScore;
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() -> SoftScore {
582        SoftScore::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, SoftScore::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, SoftScore::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, SoftScore::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, SoftScore::of(-10));
606        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::add_move_index(&mut forager, 1, SoftScore::of(-5)); // Best
607        <AcceptedCountForager<DummySolution> as LocalSearchForager<DummySolution, TestMove>>::add_move_index(&mut forager, 2, SoftScore::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, SoftScore::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, SoftScore::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, SoftScore::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, SoftScore::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, SoftScore::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, SoftScore::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, SoftScore::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, SoftScore::of(-1));
694    }
695
696    #[test]
697    fn test_first_best_score_improving_quits_on_improvement() {
698        let best = SoftScore::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, SoftScore::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, SoftScore::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, SoftScore::of(-5));
737    }
738
739    #[test]
740    fn test_first_last_step_improving_quits_on_improvement() {
741        let last_step = SoftScore::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, SoftScore::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, SoftScore::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, SoftScore::of(-5));
780    }
781}
solverforge_solver/phase/localsearch/forager.rs

solverforge_solver/phase/localsearch/
forager.rs
