solverforge-solver 0.8.5

/* Diminished returns termination.

Terminates when the rate of score improvement drops below a threshold.
*/

use std::cell::RefCell;
use std::collections::VecDeque;
use std::fmt::Debug;
use std::marker::PhantomData;
use std::time::Duration;

use solverforge_core::domain::PlanningSolution;
use solverforge_core::score::Score;
use solverforge_scoring::Director;

use super::Termination;
use crate::scope::ProgressCallback;
use crate::scope::SolverScope;

/// Terminates when the rate of score improvement falls below a threshold.
///
/// Tracks score improvements over a sliding time window and terminates
/// when the improvement rate drops below a minimum, indicating diminished
/// returns from continued optimization.
///
/// # Example
///
/// ```
/// use std::time::Duration;
/// use solverforge_solver::termination::DiminishedReturnsTermination;
/// use solverforge_core::score::SoftScore;
/// use solverforge_core::domain::PlanningSolution;
///
/// #[derive(Clone)]
/// struct MySolution;
/// impl PlanningSolution for MySolution {
///     type Score = SoftScore;
///     fn score(&self) -> Option<Self::Score> { None }
///     fn set_score(&mut self, _: Option<Self::Score>) {}
/// }
///
/// // Terminate when improvement rate falls below 0.1 per second over a 10s window
/// let term = DiminishedReturnsTermination::<MySolution>::new(
///     Duration::from_secs(10),
///     0.1,
/// );
/// ```
pub struct DiminishedReturnsTermination<S: PlanningSolution> {
    // Time window for measuring improvement rate.
    window: Duration,
    // Minimum improvement rate (score units per second) below which to terminate.
    min_rate: f64,
    // Internal state tracking improvements.
    state: RefCell<DiminishedState<S::Score>>,
    _phantom: PhantomData<fn() -> S>,
}

impl<S: PlanningSolution> Debug for DiminishedReturnsTermination<S> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("DiminishedReturnsTermination")
            .field("window", &self.window)
            .field("min_rate", &self.min_rate)
            .finish()
    }
}

struct DiminishedState<Sc: Score> {
    // Score samples within the window: (timestamp, score).
    samples: VecDeque<(Duration, Sc)>,
    // Timestamp of first sample for initial grace period.
    start_elapsed: Option<Duration>,
    // Oldest score seen — retained as baseline even after window eviction.
    baseline: Option<(Duration, Sc)>,
}

impl<Sc: Score> Default for DiminishedState<Sc> {
    fn default() -> Self {
        Self {
            samples: VecDeque::new(),
            start_elapsed: None,
            baseline: None,
        }
    }
}

impl<S: PlanningSolution> DiminishedReturnsTermination<S> {
    /// Creates a new diminished returns termination.
    ///
    /// # Arguments
    /// * `window` - Time window for measuring improvement rate
    /// * `min_rate` - Minimum improvement rate (score units per second)
    pub fn new(window: Duration, min_rate: f64) -> Self {
        Self {
            window,
            min_rate,
            state: RefCell::new(DiminishedState::default()),
            _phantom: PhantomData,
        }
    }

    /// Creates with a window in seconds.
    pub fn with_seconds(window_secs: u64, min_rate: f64) -> Self {
        Self::new(Duration::from_secs(window_secs), min_rate)
    }
}

// Safety: The RefCell is only accessed from within is_terminated,
// which is called from a single thread during solving.
unsafe impl<S: PlanningSolution> Send for DiminishedReturnsTermination<S> {}

impl<S: PlanningSolution, D: Director<S>, BestCb: ProgressCallback<S>> Termination<S, D, BestCb>
    for DiminishedReturnsTermination<S>
{
    fn is_terminated(&self, solver_scope: &SolverScope<S, D, BestCb>) -> bool {
        let Some(current_score) = solver_scope.best_score() else {
            return false; // No score yet
        };

        let mut state = self.state.borrow_mut();
        let now = solver_scope.elapsed().unwrap_or_default();

        // Initialize start time on first call
        if state.start_elapsed.is_none() {
            state.start_elapsed = Some(now);
        }

        // Don't terminate during the initial grace period (first window)
        if now.saturating_sub(state.start_elapsed.unwrap()) < self.window {
            // Record the sample; first sample becomes the baseline
            if state.baseline.is_none() {
                state.baseline = Some((now, *current_score));
            }
            state.samples.push_back((now, *current_score));
            return false;
        }

        // Remove samples outside the window
        let cutoff = now.saturating_sub(self.window);
        while let Some((time, _)) = state.samples.front() {
            if *time < cutoff {
                state.samples.pop_front();
            } else {
                break;
            }
        }

        // Add current sample
        state.samples.push_back((now, *current_score));

        /* Use oldest available reference: whichever of the in-window front or the
        baseline is older. The baseline is the first sample ever recorded (during
        the grace period) and is never evicted, so it provides a stable reference
        even when macOS timer slop causes all window samples to be evicted.
        */
        let reference = match (state.samples.front(), state.baseline.as_ref()) {
            (Some(w), Some(b)) => {
                if b.0 <= w.0 {
                    b
                } else {
                    w
                }
            }
            (Some(w), None) => w,
            (None, Some(b)) => b,
            (None, None) => return false,
        };
        let (oldest_time, oldest_score) = reference;
        let elapsed = now.saturating_sub(*oldest_time).as_secs_f64();

        if elapsed < 0.001 {
            return false; // Avoid division by near-zero
        }

        // Use the last (lowest priority / soft) level for rate calculation
        // This is the optimization objective being improved after feasibility
        let current_levels = current_score.to_level_numbers();
        let oldest_levels = oldest_score.to_level_numbers();

        /* Use the last level (soft score) for improvement rate
        For SoftScore: the only value
        For HardSoftScore: the soft value
        */
        let current_value = *current_levels.last().unwrap_or(&0);
        let oldest_value = *oldest_levels.last().unwrap_or(&0);

        // Improvement = current - oldest (positive is better)
        let improvement = (current_value - oldest_value) as f64;
        let rate = improvement / elapsed;

        // Terminate if rate is below threshold
        rate < self.min_rate
    }
}

#[cfg(test)]
#[path = "diminished_returns_tests.rs"]
mod tests;