bin-packing 0.3.0

//! Auto-strategy for 3D bin packing.
//!
//! Runs a tiered multi-strategy sweep and returns the best solution under
//! [`ThreeDSolution::is_better_than`].
//!
//! **Tier 1 — fast sweep** (always): six deterministic construction
//! heuristics are run (in parallel when the `parallel` feature is
//! enabled) and the best result is kept.
//!
//! **Tier 2 — meta sweep** (when `options.multistart_runs > 0`): the
//! `MultiStart` and `LocalSearch` meta-strategies are added to the
//! candidate pool.
//!
//! If every candidate call errors, the last error is propagated. Otherwise
//! the best non-erroring result is returned with the winning leaf
//! algorithm preserved and a diagnostic note added to
//! `solution.metrics.notes`.

use super::model::{ThreeDOptions, ThreeDProblem, ThreeDSolution};
use crate::Result;

/// Run each solver function against `(problem, options)`, parallelising with
/// rayon when the `parallel` feature is enabled and multiple cores exist.
fn run_candidates(
    candidates: &[SolverFn],
    problem: &ThreeDProblem,
    options: &ThreeDOptions,
) -> Vec<Result<ThreeDSolution>> {
    #[cfg(feature = "parallel")]
    if crate::parallel::use_parallel() {
        use rayon::prelude::*;
        return candidates.par_iter().map(|solver| solver(problem, options)).collect();
    }

    candidates.iter().map(|solver| solver(problem, options)).collect()
}

/// Solve a 3D bin-packing problem by trying several algorithms and returning
/// the best result under [`ThreeDSolution::is_better_than`].
///
/// # Errors
///
/// Propagates an error only if *every* candidate algorithm call fails.
pub(super) fn solve_auto(
    problem: &ThreeDProblem,
    options: &ThreeDOptions,
) -> Result<ThreeDSolution> {
    if options.guillotine_required {
        return solve_auto_guillotine(problem, options);
    }

    // Tier 1: fast deterministic construction heuristics.
    // Tier 2 (multistart_runs > 0): meta-strategies appended to the pool.
    let mut all_candidates: Vec<SolverFn> = vec![
        super::extreme_points::solve_extreme_points,
        super::extreme_points::solve_extreme_points_residual_space,
        super::extreme_points::solve_extreme_points_contact_point,
        super::guillotine::solve_guillotine_3d,
        super::layer::solve_layer_building,
        super::sorted::solve_first_fit_decreasing_volume,
    ];
    if options.multistart_runs > 0 {
        all_candidates.push(super::multi_start::solve_multi_start);
        all_candidates.push(super::local_search::solve_local_search);
    }

    let results = run_candidates(&all_candidates, problem, options);
    let total = results.len();

    // Collect successful results, tracking last error for fallback.
    let mut best: Option<ThreeDSolution> = None;
    let mut last_error: Option<crate::BinPackingError> = None;

    for result in results {
        match result {
            Ok(sol) => {
                let is_better = best.as_ref().is_none_or(|b| sol.is_better_than(b));
                if is_better {
                    best = Some(sol);
                }
            }
            Err(e) => {
                last_error = Some(e);
            }
        }
    }

    match best {
        Some(mut sol) => {
            let winning_alg = sol.algorithm.clone();
            sol.metrics
                .notes
                .push(format!("auto: tried {total} algorithms, best was {winning_alg}"));
            Ok(sol)
        }
        None => Err(last_error.unwrap_or_else(|| {
            crate::BinPackingError::Unsupported(
                "auto: no candidate algorithms were run".to_string(),
            )
        })),
    }
}

type SolverFn = fn(&ThreeDProblem, &ThreeDOptions) -> Result<ThreeDSolution>;

fn solve_auto_guillotine(
    problem: &ThreeDProblem,
    options: &ThreeDOptions,
) -> Result<ThreeDSolution> {
    let candidates: Vec<SolverFn> = vec![
        super::guillotine::solve_guillotine_3d,
        super::guillotine::solve_guillotine_3d_best_short_side_fit,
        super::guillotine::solve_guillotine_3d_best_long_side_fit,
        super::guillotine::solve_guillotine_3d_shorter_leftover_axis,
        super::guillotine::solve_guillotine_3d_longer_leftover_axis,
        super::guillotine::solve_guillotine_3d_min_volume_split,
        super::guillotine::solve_guillotine_3d_max_volume_split,
        super::layer::solve_layer_building_guillotine,
    ];

    let total = candidates.len();
    let results = run_candidates(&candidates, problem, options);

    let mut best: Option<ThreeDSolution> = None;
    let mut last_error: Option<crate::BinPackingError> = None;

    for result in results {
        match result {
            Ok(sol) if sol.guillotine => {
                if best.as_ref().is_none_or(|current| sol.is_better_than(current)) {
                    best = Some(sol);
                }
            }
            Ok(_sol) => {}
            Err(err) => last_error = Some(err),
        }
    }

    match best {
        Some(mut sol) => {
            let winning_alg = sol.algorithm.clone();
            sol.metrics.notes.push(format!(
                "auto: tried {total} guillotine algorithms, best was {winning_alg}",
            ));
            Ok(sol)
        }
        None => Err(last_error.unwrap_or_else(|| {
            crate::BinPackingError::Unsupported(
                "auto: no guillotine-compatible candidate succeeded".to_string(),
            )
        })),
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::three_d::model::{Bin3D, BoxDemand3D, RotationMask3D, ThreeDProblem};

    fn simple_problem() -> ThreeDProblem {
        ThreeDProblem {
            bins: vec![Bin3D {
                name: "bin".to_string(),
                width: 10,
                height: 10,
                depth: 10,
                cost: 1.0,
                quantity: None,
            }],
            demands: vec![BoxDemand3D {
                name: "box".to_string(),
                width: 5,
                height: 5,
                depth: 5,
                quantity: 1,
                allowed_rotations: RotationMask3D::ALL,
            }],
        }
    }

    #[test]
    fn auto_does_not_error_on_simple_problem() {
        let problem = simple_problem();
        let options = ThreeDOptions::default();
        let result = solve_auto(&problem, &options);
        assert!(result.is_ok(), "expected Ok, got {result:?}");
    }

    #[test]
    fn auto_preserves_winning_leaf_algorithm() {
        let problem = simple_problem();
        let options = ThreeDOptions::default();
        let solution = solve_auto(&problem, &options).expect("solve_auto should succeed");
        assert_ne!(solution.algorithm, "auto");
        assert!(!solution.algorithm.is_empty());
    }

    #[test]
    fn auto_adds_diagnostic_note() {
        let problem = simple_problem();
        let options = ThreeDOptions::default();
        let solution = solve_auto(&problem, &options).expect("solve_auto should succeed");
        let has_note = solution.metrics.notes.iter().any(|n| n.starts_with("auto: tried "));
        assert!(has_note, "expected diagnostic note, got {:?}", solution.metrics.notes);
    }

    #[test]
    fn auto_guillotine_required_returns_guillotine_solution() {
        let problem = simple_problem();
        let options = ThreeDOptions { guillotine_required: true, ..ThreeDOptions::default() };
        let solution = solve_auto(&problem, &options).expect("solve_auto should succeed");
        assert!(solution.guillotine);
        assert_ne!(solution.algorithm, "auto");
    }

    /// Auto mode with multistart enabled exercises parallel tier-2 dispatch.
    #[test]
    fn auto_with_multistart_runs_tier2_candidates() {
        let problem = ThreeDProblem {
            bins: vec![Bin3D {
                name: "bin".to_string(),
                width: 10,
                height: 10,
                depth: 10,
                cost: 1.0,
                quantity: None,
            }],
            demands: vec![
                BoxDemand3D {
                    name: "a".to_string(),
                    width: 5,
                    height: 5,
                    depth: 5,
                    quantity: 2,
                    allowed_rotations: RotationMask3D::ALL,
                },
                BoxDemand3D {
                    name: "b".to_string(),
                    width: 3,
                    height: 3,
                    depth: 3,
                    quantity: 4,
                    allowed_rotations: RotationMask3D::ALL,
                },
            ],
        };
        let options =
            ThreeDOptions { multistart_runs: 4, seed: Some(42), ..ThreeDOptions::default() };
        let solution = solve_auto(&problem, &options).expect("auto with multistart");
        assert!(solution.unplaced.is_empty());
        assert!(solution.metrics.notes.iter().any(|n| n.starts_with("auto: tried ")));
    }

    /// Running auto twice with the same problem produces the same result.
    #[test]
    fn auto_is_deterministic() {
        let problem = simple_problem();
        let options =
            ThreeDOptions { multistart_runs: 2, seed: Some(7), ..ThreeDOptions::default() };
        let first = solve_auto(&problem, &options).expect("first");
        let second = solve_auto(&problem, &options).expect("second");
        assert_eq!(first.bin_count, second.bin_count);
        assert_eq!(first.algorithm, second.algorithm);
        assert_eq!(first.total_waste_volume, second.total_waste_volume);
        assert_eq!(first.total_cost, second.total_cost);
        assert_eq!(first.unplaced.len(), second.unplaced.len());
    }
}