basin 0.12.0

//! Termination layer: the [`TerminationCriterion`] trait and the
//! framework-level criteria solvers can be terminated by. Each criterion
//! bounds on the minimum state shape it needs (tenet 3 in `CONTRIBUTING.md`),
//! so mismatches are compile errors rather than runtime no-ops.

use web_time::{Duration, Instant};

use crate::core::constraint::BoxConstraints;
use crate::core::math::{ClampInPlace, NormInfinity, NormSquared, Scalar, ScaledAdd, VectorLen};
use crate::core::state::{CmaEsState, GradientState, SimplexState, State};

/// Why the executor stopped. Returned on
/// [`OptimizationResult::reason`](crate::core::executor::OptimizationResult::reason)
/// and the various step / run hooks.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum TerminationReason {
    /// `state.iter() >= max_iter`.
    MaxIter,
    /// Cost-evaluation budget exhausted.
    MaxCostEvals,
    /// Gradient-evaluation budget exhausted.
    MaxGradientEvals,
    /// `‖∇f(x)‖ ≤ tol`.
    GradientTolerance,
    /// `‖∇f(x_k)‖ ≤ tol · ‖∇f(x_0)‖` — gradient norm relative to the
    /// initial gradient (scale-invariant first-order stationarity).
    RelativeGradientTolerance,
    /// `‖x − π_C(x − ∇f(x))‖_∞ ≤ tol` — projected-gradient stationarity
    /// for box-constrained problems. Collapses to the unconstrained
    /// gradient norm when no constraint is active.
    ProjectedGradientTolerance,
    /// `‖x_k − x_{k−1}‖ ≤ tol`.
    ParamTolerance,
    /// `‖x_k − x_{k−1}‖ ≤ tol · ‖x_k‖` — scale-invariant step test
    /// (MINPACK `xtol`).
    RelativeParamTolerance,
    /// `|f_k − f_{k−1}| ≤ tol`.
    CostTolerance,
    /// `|f_k − f_{k−1}| ≤ tol · |f_{k−1}|` — scale-invariant cost
    /// reduction test (MINPACK `ftol`).
    RelativeCostTolerance,
    /// `f(x_k) ≤ target` — user-supplied target cost reached
    /// (NLopt's `stopval` / SciPy's `f_min`).
    TargetCost,
    /// Best-so-far cost has not improved by more than `tol` in
    /// `patience` consecutive iterations — the early-stopping pattern.
    NoImprovement,
    /// Simplex collapsed below the configured tolerance.
    SimplexTolerance,
    /// CMA-ES search distribution collapsed below TolX:
    /// `σ · maxᵢ dᵢ < tol_x` (Hansen 2016 Appendix B.3).
    CmaEsTolerance,
    /// Wall-clock time limit reached.
    MaxTime,
    /// Solver determined it has converged (e.g. fixed point reached).
    SolverConverged,
    /// Solver cannot make further progress (e.g. line search failure).
    SolverFailed,
}

impl TerminationReason {
    /// Whether this reason represents an unrecoverable failure that an
    /// outer solver should bubble (rather than consume and continue).
    ///
    /// Currently only [`SolverFailed`](Self::SolverFailed) qualifies —
    /// [`MaxIter`](Self::MaxIter), the `*Tolerance` reasons, and
    /// [`SolverConverged`](Self::SolverConverged) are all "clean stops"
    /// that an outer solver running an inner per outer iter should treat
    /// as "result is fine, move on". See `CONTRIBUTING.md` "Solver
    /// composition" for the failure-routing contract.
    pub fn is_failure(&self) -> bool {
        matches!(self, Self::SolverFailed)
    }
}

/// A pluggable termination check evaluated by the executor.
///
/// # Contract
///
/// - **Caller must:** register criteria with
///   [`Executor::terminate_on`](crate::core::executor::Executor::terminate_on)
///   before calling [`Executor::run`](crate::core::executor::Executor::run).
///   Insertion order matters: criteria are checked in the order they
///   were registered, and the **first to return `Some(_)` halts the run**.
///   The built-in [`MaxIter`] limit (settable via
///   [`Executor::max_iter`](crate::core::executor::Executor::max_iter))
///   is checked *before* user criteria each iteration.
/// - **Caller must:** rely on the bound on `S` to encode capability:
///   e.g. [`GradientTolerance`] requires `S: GradientState`, so handing
///   it to a derivative-free solver is a compile error, not a runtime
///   "N/A" (tenet 3 in `CONTRIBUTING.md`).
/// - **Implementor must:** treat [`check`](Self::check) as side-effect
///   free *with respect to the optimization*. Internal state for criteria
///   that need history (e.g. [`ParamTolerance`], [`CostTolerance`])
///   lives inside the criterion itself.
/// - Criteria are checked *before* each iteration including iter 0 so
///   an already-optimal initial point exits immediately. See the
///   [`executor`](crate::core::executor) module docs for the full
///   per-iteration ordering.
pub trait TerminationCriterion<S> {
    /// Inspect the current state and return `Some(reason)` to halt the
    /// run, or `None` to continue. Called once per iteration before the
    /// solver's `next_iter`.
    fn check(&mut self, state: &S) -> Option<TerminationReason>;

    /// Reset any internal per-run state so the criterion behaves as if
    /// freshly constructed.
    ///
    /// The driver calls this once at the start of every run (see
    /// [`run_loop`](crate::core::executor::run_loop)), so a single criterion
    /// instance reused across composed inner runs — as an
    /// [`InnerExecutor`](crate::core::inner::InnerExecutor) does — sees fresh
    /// state each call. Stateless criteria need no override; any criterion
    /// holding cross-call state (a start instant, an anchored initial value, a
    /// stall counter) MUST override this to clear it, or it will misbehave when
    /// reused. The default is a no-op.
    fn reset(&mut self) {}
}

/// Stop after `state.iter() >= n` iterations.
pub struct MaxIter(pub u64);

impl<S: State> TerminationCriterion<S> for MaxIter {
    fn check(&mut self, state: &S) -> Option<TerminationReason> {
        if state.iter() >= self.0 {
            Some(TerminationReason::MaxIter)
        } else {
            None
        }
    }
}

/// Stop after `state.cost_evals() >= n` cost-function evaluations.
/// Lagarias et al. (1998) (T3) — the budget users actually care about
/// when one iteration can spend many evals (line search, Nelder-Mead
/// shrink).
pub struct MaxCostEvals(pub u64);

impl<S: State> TerminationCriterion<S> for MaxCostEvals {
    fn check(&mut self, state: &S) -> Option<TerminationReason> {
        if state.cost_evals() >= self.0 {
            Some(TerminationReason::MaxCostEvals)
        } else {
            None
        }
    }
}

/// Stop after `state.gradient_evals() >= n` gradient evaluations. Bound
/// on `S: GradientState` so it can't be paired with derivative-free
/// solvers — a compile error rather than a silently no-op criterion.
pub struct MaxGradientEvals(pub u64);

impl<S: GradientState> TerminationCriterion<S> for MaxGradientEvals {
    fn check(&mut self, state: &S) -> Option<TerminationReason> {
        if state.gradient_evals() >= self.0 {
            Some(TerminationReason::MaxGradientEvals)
        } else {
            None
        }
    }
}

/// Stop when `‖∇f(x)‖ ≤ tol`. Skipped silently when the state has no
/// gradient populated yet (e.g. iter 0 before `init` has run).
///
/// Requires `S: GradientState` — pairing with a derivative-free solver
/// is a compile error.
pub struct GradientTolerance<F = f64>(pub F);

impl<S, F> TerminationCriterion<S> for GradientTolerance<F>
where
    F: Scalar,
    S: GradientState,
    S::Param: NormSquared<F>,
{
    fn check(&mut self, state: &S) -> Option<TerminationReason> {
        let g = state.gradient()?;
        if g.norm_squared() <= self.0 * self.0 {
            Some(TerminationReason::GradientTolerance)
        } else {
            None
        }
    }
}

/// Stop when `‖∇f(x_k)‖ ≤ tol · ‖∇f(x_0)‖` — the gradient norm relative
/// to the gradient at the starting point. The scale-invariant analogue
/// of [`GradientTolerance`]: scaling the objective by a constant scales
/// every gradient by the same constant, so the ratio — and hence the
/// stopping point — is unchanged, letting one `tol` port across
/// objectives of different magnitude.
///
/// Unlike [`RelativeCostTolerance`] / [`RelativeParamTolerance`] (which
/// normalize by the *current* iterate's quantity), this normalizes by
/// the *initial* gradient. The gradient → 0 at a minimizer, so a
/// relative-to-current gradient test would be degenerate (`0/0`);
/// relative-to-initial is the standard first-order rule (`‖∇f_k‖ ≤
/// ε·‖∇f_0‖`). Pair with an absolute [`GradientTolerance`] when the
/// starting gradient may itself be tiny.
///
/// Captures `‖∇f(x_0)‖` on the first check at which a gradient is
/// populated. Requires `S: GradientState` — pairing with a
/// derivative-free solver is a compile error. Skipped silently while
/// the state has no gradient populated yet.
pub struct RelativeGradientTolerance<F = f64> {
    tol: F,
    initial_norm_squared: Option<F>,
}

impl<F: Scalar> RelativeGradientTolerance<F> {
    /// New tolerance with the given relative gradient-norm bound.
    pub fn new(tol: F) -> Self {
        Self {
            tol,
            initial_norm_squared: None,
        }
    }
}

impl<S, F> TerminationCriterion<S> for RelativeGradientTolerance<F>
where
    F: Scalar,
    S: GradientState,
    S::Param: NormSquared<F>,
{
    fn check(&mut self, state: &S) -> Option<TerminationReason> {
        let g = state.gradient()?;
        let norm_squared = g.norm_squared();
        // Anchor on the first populated gradient (the initial iterate).
        let initial = *self.initial_norm_squared.get_or_insert(norm_squared);
        // ‖∇f_k‖ ≤ tol·‖∇f_0‖ ⟺ ‖∇f_k‖² ≤ tol²·‖∇f_0‖², avoiding a sqrt.
        if norm_squared <= self.tol * self.tol * initial {
            Some(TerminationReason::RelativeGradientTolerance)
        } else {
            None
        }
    }

    fn reset(&mut self) {
        self.initial_norm_squared = None;
    }
}

/// Stop when `‖x − π_C(x − ∇f(x))‖_∞ ≤ tol`, the canonical first-order
/// optimality measure for box-constrained minimization. `π_C` is the
/// projection onto the box `[lower, upper]` carried by this criterion.
///
/// The metric is zero exactly at a KKT point of the box-constrained
/// problem: when no constraint is active it collapses to `‖∇f‖_∞`;
/// when a face is active it collapses to the ∞-norm of the gradient
/// components corresponding to *inactive* coordinates. This is why
/// [`GradientTolerance`] is the wrong metric for constrained problems —
/// `‖∇f‖` need not vanish at a constrained optimum (the gradient
/// points into an active face), but the projected-gradient measure
/// always does.
///
/// Construct from explicit bounds with [`new`](Self::new), or clone
/// them off a [`BoxConstraints`] problem with
/// [`from_problem`](Self::from_problem). The bounds are stored once at
/// construction; the criterion does not call back into the problem.
///
/// Requires `S: GradientState` and `S::Param` to implement
/// [`ScaledAdd<f64>`], [`ClampInPlace`], [`NormInfinity`], and `Clone`.
/// Skipped silently when the state has no gradient populated yet
/// (e.g. iter 0 before `init` has run).
pub struct ProjectedGradientTolerance<P, F = f64> {
    lower: P,
    upper: P,
    tol: F,
}

impl<P, F> ProjectedGradientTolerance<P, F> {
    /// New criterion with explicit bounds.
    pub fn new(lower: P, upper: P, tol: F) -> Self {
        Self { lower, upper, tol }
    }

    /// New criterion that clones its bounds off a [`BoxConstraints`]
    /// problem.
    pub fn from_problem<Pr>(problem: &Pr, tol: F) -> Self
    where
        Pr: BoxConstraints<Param = P>,
        P: Clone,
    {
        Self {
            lower: problem.lower().clone(),
            upper: problem.upper().clone(),
            tol,
        }
    }
}

impl<S, P, F> TerminationCriterion<S> for ProjectedGradientTolerance<P, F>
where
    F: Scalar,
    S: GradientState + State<Param = P>,
    P: ScaledAdd<F> + ClampInPlace + NormInfinity<F> + Clone,
{
    fn check(&mut self, state: &S) -> Option<TerminationReason> {
        let g = state.gradient()?;
        let mut probe = state.param().clone(); // x
        probe.scaled_add(-F::one(), g); // x − ∇f
        probe.clamp_in_place(&self.lower, &self.upper); // π(x − ∇f)
        probe.scaled_add(-F::one(), state.param()); // π(x − ∇f) − x
        if probe.norm_infinity() <= self.tol {
            Some(TerminationReason::ProjectedGradientTolerance)
        } else {
            None
        }
    }
}

/// Stop when `‖x_k − x_{k−1}‖ ≤ tol`. Holds its own copy of the previous
/// iterate so it doesn't depend on state-side history.
pub struct ParamTolerance<P, F = f64> {
    tol_squared: F,
    last: Option<P>,
}

impl<P, F: Scalar> ParamTolerance<P, F> {
    /// New tolerance with the given absolute step bound.
    pub fn new(tol: F) -> Self {
        Self {
            tol_squared: tol * tol,
            last: None,
        }
    }
}

impl<S, P, F> TerminationCriterion<S> for ParamTolerance<P, F>
where
    F: Scalar,
    S: State<Param = P>,
    P: ScaledAdd<F> + NormSquared<F> + Clone,
{
    fn check(&mut self, state: &S) -> Option<TerminationReason> {
        let curr = state.param();
        let triggered = if let Some(last) = &self.last {
            let mut diff = curr.clone();
            diff.scaled_add(-F::one(), last);
            diff.norm_squared() <= self.tol_squared
        } else {
            false
        };
        self.last = Some(curr.clone());
        triggered.then_some(TerminationReason::ParamTolerance)
    }

    fn reset(&mut self) {
        self.last = None;
    }
}

/// Stop when `‖x_k − x_{k−1}‖ ≤ tol · ‖x_k‖` — the scale-invariant
/// analogue of [`ParamTolerance`], matching MINPACK's `xtol`. Holds its
/// own copy of the previous iterate.
///
/// Unlike the absolute [`ParamTolerance`], the bound scales with the
/// magnitude of the iterate, so a single `tol` is portable across
/// problems whose parameters live at very different scales. Near
/// `x = 0` the relative bound collapses (the right-hand side → 0), so
/// pair it with an absolute [`ParamTolerance`] when the optimum may sit
/// at the origin.
pub struct RelativeParamTolerance<P, F = f64> {
    tol: F,
    last: Option<P>,
}

impl<P, F> RelativeParamTolerance<P, F> {
    /// New tolerance with the given relative step bound.
    pub fn new(tol: F) -> Self {
        Self { tol, last: None }
    }
}

impl<S, P, F> TerminationCriterion<S> for RelativeParamTolerance<P, F>
where
    F: Scalar,
    S: State<Param = P>,
    P: ScaledAdd<F> + NormSquared<F> + Clone,
{
    fn check(&mut self, state: &S) -> Option<TerminationReason> {
        let curr = state.param();
        let triggered = if let Some(last) = &self.last {
            let mut diff = curr.clone();
            diff.scaled_add(-F::one(), last);
            // ‖Δx‖ ≤ tol·‖x_k‖ ⟺ ‖Δx‖² ≤ tol²·‖x_k‖², avoiding a sqrt.
            diff.norm_squared() <= self.tol * self.tol * curr.norm_squared()
        } else {
            false
        };
        self.last = Some(curr.clone());
        triggered.then_some(TerminationReason::RelativeParamTolerance)
    }

    fn reset(&mut self) {
        self.last = None;
    }
}

/// Stop when `|f_k − f_{k−1}| ≤ tol`. Holds its own copy of the previous
/// cost.
pub struct CostTolerance<F = f64> {
    tol: F,
    last: Option<F>,
}

impl<F> CostTolerance<F> {
    /// New tolerance with the given absolute cost-change bound.
    pub fn new(tol: F) -> Self {
        Self { tol, last: None }
    }
}

impl<S, F> TerminationCriterion<S> for CostTolerance<F>
where
    F: Scalar,
    S: State<Float = F>,
{
    fn check(&mut self, state: &S) -> Option<TerminationReason> {
        let curr = state.cost();
        let triggered = self
            .last
            .is_some_and(|l| (l - curr).abs() <= self.tol && curr.is_finite());
        self.last = Some(curr);
        triggered.then_some(TerminationReason::CostTolerance)
    }

    fn reset(&mut self) {
        self.last = None;
    }
}

/// Stop when `|f_k − f_{k−1}| ≤ tol · |f_{k−1}|` — the scale-invariant
/// analogue of [`CostTolerance`], matching MINPACK's `ftol` (whose
/// `actred = 1 − (‖r_k‖/‖r_{k−1}‖)²` reduces to this relative-cost test
/// for `f = ½‖r‖²`). Holds its own copy of the previous cost.
///
/// The bound scales with the current cost level, so one `tol` is
/// portable across problems whose cost magnitudes differ by orders of
/// magnitude (e.g. least-squares residuals carrying different
/// normalizations). Near `f = 0` the relative bound collapses, so pair
/// it with an absolute [`CostTolerance`] when the optimum cost is zero.
pub struct RelativeCostTolerance<F = f64> {
    tol: F,
    last: Option<F>,
}

impl<F> RelativeCostTolerance<F> {
    /// New tolerance with the given relative cost-change bound.
    pub fn new(tol: F) -> Self {
        Self { tol, last: None }
    }
}

impl<S, F> TerminationCriterion<S> for RelativeCostTolerance<F>
where
    F: Scalar,
    S: State<Float = F>,
{
    fn check(&mut self, state: &S) -> Option<TerminationReason> {
        let curr = state.cost();
        let triggered = self
            .last
            .is_some_and(|l| curr.is_finite() && (l - curr).abs() <= self.tol * l.abs());
        self.last = Some(curr);
        triggered.then_some(TerminationReason::RelativeCostTolerance)
    }

    fn reset(&mut self) {
        self.last = None;
    }
}

/// Stop when `best_cost ≤ target` — a user-supplied target cost level.
/// This is NLopt's `stopval` and SciPy's `f_min`: an absolute *level*
/// stop, not a change-in-cost stop like [`CostTolerance`].
///
/// Most useful for global / stochastic solvers (random search, CMA-ES,
/// the steady-state GA) where "good enough" is a more natural stopping
/// rule than asymptotic convergence, and for benchmarking
/// ("how long until the solver hits cost ≤ ε?").
///
/// Binds on [`State::best_cost`] — the lowest cost the executor has
/// ever observed on this state — so on non-monotone solvers (Brent's
/// rejected probes, a line search that allows transient increases,
/// CMA-ES sampling) this fires once any iterate dropped to the
/// target, never on a transient uphill step away from a previously
/// reached target.
pub struct TargetCost<F = f64>(pub F);

impl<S, F> TerminationCriterion<S> for TargetCost<F>
where
    F: Scalar,
    S: State<Float = F>,
{
    fn check(&mut self, state: &S) -> Option<TerminationReason> {
        (state.best_cost() <= self.0).then_some(TerminationReason::TargetCost)
    }
}

/// Stop when the executor-maintained best cost has not improved by
/// more than `tol` in `patience` consecutive checks — the early-
/// stopping pattern from ML, minus the validation set.
///
/// Improvement is counted strictly against a running anchor: an
/// observation counts as improvement iff
/// `state.best_cost() < anchor − tol`. So `tol` is the minimum drop
/// that resets the patience counter (Keras calls this `min_delta`).
/// `tol = 0.0` means "any strict decrease resets".
///
/// Most useful for stochastic / global / non-monotone solvers (random
/// search, CMA-ES, the steady-state GA, future basin-hopping) and for
/// non-monotone single-iterate solvers (Brent's rejected probes) where
/// the one-step [`CostTolerance`] family fires spuriously on accidental
/// small `|Δf|`. Binds on [`State::best_cost`], which is monotone
/// non-increasing by construction (executor-maintained), so the
/// "improvement" check has the same meaning across every state shape.
pub struct NoImprovement<F = f64> {
    patience: u64,
    tol: F,
    /// Last `best_cost()` value that counted as improvement —
    /// resets the patience counter on the next strict drop below
    /// `anchor − tol`.
    anchor: Option<F>,
    stalled: u64,
}

impl<F> NoImprovement<F> {
    /// New criterion that fires after `patience` consecutive checks
    /// without an improvement of more than `tol`.
    pub fn new(patience: u64, tol: F) -> Self {
        Self {
            patience,
            tol,
            anchor: None,
            stalled: 0,
        }
    }
}

impl<S, F> TerminationCriterion<S> for NoImprovement<F>
where
    F: Scalar,
    S: State<Float = F>,
{
    fn check(&mut self, state: &S) -> Option<TerminationReason> {
        let curr = state.best_cost();
        let improved = match self.anchor {
            None => curr.is_finite(),
            Some(anchor) => curr.is_finite() && curr < anchor - self.tol,
        };
        if improved {
            self.anchor = Some(curr);
            self.stalled = 0;
            None
        } else {
            self.stalled += 1;
            (self.stalled >= self.patience).then_some(TerminationReason::NoImprovement)
        }
    }

    fn reset(&mut self) {
        self.anchor = None;
        self.stalled = 0;
    }
}

/// Simplex-collapse test for simplex-based solvers (e.g. Nelder-Mead),
/// per Lagarias et al. (1998), eq. (T1):
///
/// stop when `max_i ‖x_i − x_1‖_∞ ≤ tol_x` **and**
/// `max_i |f_i − f_1| ≤ tol_f`, where `x_1` / `f_1` are the best vertex
/// and its cost.
///
/// Requires `S: SimplexState` — single-iterate solvers (gradient
/// descent, BFGS) cannot be paired with it (compile error).
pub struct SimplexTolerance<F = f64> {
    tol_x: F,
    tol_f: F,
}

impl<F> SimplexTolerance<F> {
    /// New tolerance with separate vertex and cost bounds.
    pub fn new(tol_x: F, tol_f: F) -> Self {
        Self { tol_x, tol_f }
    }
}

impl<S, F> TerminationCriterion<S> for SimplexTolerance<F>
where
    F: Scalar,
    S: SimplexState<Float = F>,
    S::Param: Clone + ScaledAdd<F> + NormInfinity<F>,
{
    fn check(&mut self, state: &S) -> Option<TerminationReason> {
        let vertices = state.vertices();
        let costs = state.costs();
        let best = &vertices[0];
        let best_cost = costs[0];

        for x_i in &vertices[1..] {
            let mut diff = x_i.clone();
            diff.scaled_add(-F::one(), best);
            if diff.norm_infinity() > self.tol_x {
                return None;
            }
        }
        for &f_i in &costs[1..] {
            if (f_i - best_cost).abs() > self.tol_f {
                return None;
            }
        }
        Some(TerminationReason::SimplexTolerance)
    }
}

/// CMA-ES TolX convergence test (Hansen 2016 Appendix B.3): stop when
/// the largest standard deviation of any axis of the search
/// distribution drops below `tol_x`, i.e. `σ · maxᵢ dᵢ < tol_x` (where
/// `dᵢ` are the square roots of `C`'s eigenvalues).
///
/// Binds on the concrete [`CmaEsState`] — the canonical convergence
/// criterion for both [`CmaEs`](crate::solver::CmaEs) and
/// [`BoundedCmaEs`](crate::solver::BoundedCmaEs), which share that
/// state. The Hansen-recommended default is `1e−12 · initial_sigma`
/// (scaled by `maxᵢ stdsᵢ` when an anisotropic initial covariance is
/// used, to stay relative to the initial spread).
pub struct CmaEsTolerance<F = f64> {
    tol_x: F,
}

impl<F> CmaEsTolerance<F> {
    /// New TolX criterion firing at `σ · maxᵢ dᵢ < tol_x`.
    pub fn new(tol_x: F) -> Self {
        Self { tol_x }
    }
}

impl<V, M, F> TerminationCriterion<CmaEsState<V, M, F>> for CmaEsTolerance<F>
where
    F: Scalar,
    V: VectorLen + std::ops::Index<usize, Output = F>,
{
    fn check(&mut self, state: &CmaEsState<V, M, F>) -> Option<TerminationReason> {
        (state.sigma() * state.max_axis_std() < self.tol_x)
            .then_some(TerminationReason::CmaEsTolerance)
    }
}

/// Stop after wall-clock time `limit` has elapsed since the first `check`.
///
/// Uses `web-time::Instant` so it works on both native and
/// `wasm32-unknown-unknown` without feature gating.
pub struct MaxTime {
    limit: Duration,
    start: Option<Instant>,
}

impl MaxTime {
    /// New wall-clock limit. The clock starts on the first `check`.
    pub fn new(limit: Duration) -> Self {
        Self { limit, start: None }
    }
}

impl<S> TerminationCriterion<S> for MaxTime {
    fn check(&mut self, _state: &S) -> Option<TerminationReason> {
        let start = *self.start.get_or_insert_with(Instant::now);
        if start.elapsed() >= self.limit {
            Some(TerminationReason::MaxTime)
        } else {
            None
        }
    }

    fn reset(&mut self) {
        self.start = None;
    }
}

#[cfg(test)]
mod reset_tests {
    //! `reset` must restore each stateful criterion to its
    //! freshly-constructed behaviour, so a criterion reused across
    //! composed inner runs (where `run_loop` calls `reset` at the start of
    //! every run) does not carry state across calls. The assertions are
    //! chosen so that the *unreset* behaviour would differ — i.e. each test
    //! fails if the `reset` override is removed.
    use super::*;
    use crate::core::state::BasicState;

    type S = BasicState<Vec<f64>>;

    #[test]
    fn relative_gradient_tolerance_reanchors_after_reset() {
        // tol 0.1 → fires when ‖∇f_k‖² ≤ 0.01·anchor.
        let mut c = RelativeGradientTolerance::new(0.1_f64);
        let mut state: S = BasicState::new(vec![0.0]);

        // Anchor on a large gradient (‖∇‖² = 100): doesn't fire.
        state.gradient = Some(vec![10.0]);
        assert!(TerminationCriterion::<S>::check(&mut c, &state).is_none());

        TerminationCriterion::<S>::reset(&mut c);

        // Re-anchor on a small gradient (‖∇‖² = 0.25). Relative to the new
        // anchor the ratio is 1 ≫ 0.01, so it must NOT fire. If the anchor
        // had carried over (100), 0.25 ≤ 0.01·100 = 1 would fire.
        state.gradient = Some(vec![0.5]);
        assert!(
            TerminationCriterion::<S>::check(&mut c, &state).is_none(),
            "reset should re-anchor ‖∇f_0‖ to this run's initial gradient"
        );
    }

    #[test]
    fn no_improvement_clears_stall_counter_after_reset() {
        // patience 2: fires after 2 consecutive non-improving checks.
        let mut c = NoImprovement::new(2, 0.0_f64);
        let mut state: S = BasicState::new(vec![0.0]);
        state.best_cost = 10.0;

        // First check anchors at 10 (counts as improvement), second stalls
        // once. One more stall (without a reset) would fire.
        assert!(TerminationCriterion::<S>::check(&mut c, &state).is_none());
        assert!(TerminationCriterion::<S>::check(&mut c, &state).is_none());

        TerminationCriterion::<S>::reset(&mut c);

        // After reset the anchor is cleared, so this counts as a fresh
        // improvement → no fire. Without reset, the stall counter would
        // reach the patience of 2 here and fire.
        assert!(
            TerminationCriterion::<S>::check(&mut c, &state).is_none(),
            "reset should clear the anchor and stall counter"
        );
    }

    #[test]
    fn max_time_restarts_clock_after_reset() {
        let mut c = MaxTime::new(Duration::from_millis(20));

        // Prime the clock, then let it elapse past the limit so it fires.
        assert!(TerminationCriterion::<()>::check(&mut c, &()).is_none());
        std::thread::sleep(Duration::from_millis(40));
        assert_eq!(
            TerminationCriterion::<()>::check(&mut c, &()),
            Some(TerminationReason::MaxTime)
        );

        TerminationCriterion::<()>::reset(&mut c);

        // The clock restarts on the next check; ~0 ms elapsed < 20 ms limit.
        assert!(
            TerminationCriterion::<()>::check(&mut c, &()).is_none(),
            "reset should restart the wall-clock from the next check"
        );
    }
}