u_nesting_d3/

packer.rs

//! 3D bin packing solver.

use crate::boundary::Boundary3D;
use crate::brkga_packing::run_brkga_packing;
use crate::extreme_point::run_ep_packing;
use crate::ga_packing::run_ga_packing;
use crate::geometry::Geometry3D;
use crate::physics::{PhysicsConfig, PhysicsSimulator};
use crate::sa_packing::run_sa_packing;
use crate::stability::{PlacedBox, StabilityAnalyzer, StabilityConstraint, StabilityReport};
use u_nesting_core::brkga::BrkgaConfig;
use u_nesting_core::ga::GaConfig;
use u_nesting_core::geom::nalgebra_types::{NaPoint3 as Point3, NaVector3 as Vector3};
use u_nesting_core::geometry::{Boundary, Geometry};
use u_nesting_core::sa::SaConfig;
use u_nesting_core::solver::{Config, ProgressCallback, ProgressInfo, Solver, Strategy};
use u_nesting_core::{Placement, Result, SolveResult};

use std::sync::atomic::{AtomicBool, Ordering};
use std::sync::Arc;
use u_nesting_core::timing::Timer;

/// Best fit candidate for 3D placement.
/// (orientation_idx, width, depth, height, place_x, place_y, place_z, new_row_depth, new_layer_height)
type BestFit3D = Option<(usize, f64, f64, f64, f64, f64, f64, f64, f64)>;

/// 3D bin packing solver.
pub struct Packer3D {
    config: Config,
    cancelled: Arc<AtomicBool>,
}

impl Packer3D {
    /// Creates a new packer with the given configuration.
    pub fn new(config: Config) -> Self {
        Self {
            config,
            cancelled: Arc::new(AtomicBool::new(false)),
        }
    }

    /// Creates a packer with default configuration.
    pub fn default_config() -> Self {
        Self::new(Config::default())
    }

    /// Validates the stability of a packing result.
    ///
    /// Analyzes each placement to ensure boxes are properly supported.
    pub fn validate_stability(
        &self,
        result: &SolveResult<f64>,
        geometries: &[Geometry3D],
        _boundary: &Boundary3D,
        constraint: StabilityConstraint,
    ) -> StabilityReport {
        // Convert placements to PlacedBox format
        let placed_boxes = self.placements_to_boxes(result, geometries);
        let analyzer = StabilityAnalyzer::new(constraint);
        analyzer.analyze(&placed_boxes, 0.0)
    }

    /// Validates stability using physics simulation.
    ///
    /// Runs a physics simulation to detect boxes that would fall or tip.
    pub fn validate_stability_physics(
        &self,
        result: &SolveResult<f64>,
        geometries: &[Geometry3D],
        boundary: &Boundary3D,
    ) -> StabilityReport {
        let placed_boxes = self.placements_to_boxes(result, geometries);
        let container = Vector3::new(boundary.width(), boundary.depth(), boundary.height());

        let config = PhysicsConfig::default().with_max_time(2.0);
        let simulator = PhysicsSimulator::new(config);
        simulator.validate_stability(&placed_boxes, container, 0.0)
    }

    /// Enforces the boundary's gravity/stability constraints on a finished packing.
    ///
    /// Strategies optimise for volume, not support, so a result may contain boxes that
    /// float or rest on too little base. When the boundary requests gravity and/or
    /// stability, this removes the offending boxes (moving them to `unplaced`) so the
    /// returned packing actually satisfies the constraint the caller asked for — rather
    /// than the flags being silently ignored.
    ///
    /// Removal iterates: dropping a box can leave the boxes it supported unsupported, so
    /// the result is re-validated until every remaining box is stable.
    fn enforce_support(
        &self,
        result: &mut SolveResult<f64>,
        geometries: &[Geometry3D],
        boundary: &Boundary3D,
    ) {
        // Stability is the stronger requirement (a real base-support ratio); plain
        // gravity only forbids floating, i.e. demands any positive contact below.
        let constraint = if boundary.has_stability() {
            StabilityConstraint::partial_base(0.7)
        } else {
            StabilityConstraint::partial_base(1e-6)
        };

        // The pack rests boxes on z = margin (the inset floor), so the support analysis
        // must use that as the floor — checking against z = 0 would read every bottom
        // box as floating and drop the whole pack when margin > 0.
        let floor_z = self.config.margin;
        let analyzer = StabilityAnalyzer::new(constraint);
        while !result.placements.is_empty() {
            let placed_boxes = self.placements_to_boxes(result, geometries);
            let report = analyzer.analyze(&placed_boxes, floor_z);
            if report.is_all_stable() {
                break;
            }
            let drop: std::collections::HashSet<(String, usize)> = report
                .unstable_boxes()
                .iter()
                .map(|r| (r.id.clone(), r.instance))
                .collect();
            result
                .placements
                .retain(|p| !drop.contains(&(p.geometry_id.clone(), p.instance)));
            for (id, _) in drop {
                result.unplaced.push(id);
            }
        }

        result.deduplicate_unplaced();
        // Placed volume shrank, so the reported utilization must follow.
        let boxes = self.placements_to_boxes(result, geometries);
        let placed_volume: f64 = boxes
            .iter()
            .map(|b| b.dimensions.x * b.dimensions.y * b.dimensions.z)
            .sum();
        let container_volume = boundary.measure();
        result.utilization = if container_volume > 0.0 {
            placed_volume / container_volume
        } else {
            0.0
        };
    }

    /// Converts placements to PlacedBox format for stability analysis.
    fn placements_to_boxes(
        &self,
        result: &SolveResult<f64>,
        geometries: &[Geometry3D],
    ) -> Vec<PlacedBox> {
        let geom_map: std::collections::HashMap<&str, &Geometry3D> =
            geometries.iter().map(|g| (g.id().as_str(), g)).collect();

        result
            .placements
            .iter()
            .filter_map(|p| {
                let geom = geom_map.get(p.geometry_id.as_str())?;
                let ori_idx = p.rotation_index.unwrap_or(0);
                let dims = geom.dimensions_for_orientation(ori_idx);

                let mut placed = PlacedBox::new(
                    p.geometry_id.clone(),
                    p.instance,
                    Point3::new(p.position[0], p.position[1], p.position[2]),
                    dims,
                );

                if let Some(mass) = geom.mass() {
                    placed = placed.with_mass(mass);
                }

                Some(placed)
            })
            .collect()
    }

    /// Simple layer-based packing algorithm.
    fn layer_packing(
        &self,
        geometries: &[Geometry3D],
        boundary: &Boundary3D,
    ) -> Result<SolveResult<f64>> {
        let start = Timer::now();
        let mut result = SolveResult::new();
        let mut placements = Vec::new();

        let margin = self.config.margin;
        let spacing = self.config.spacing;

        let bound_max_x = boundary.width() - margin;
        let bound_max_y = boundary.depth() - margin;
        let bound_max_z = boundary.height() - margin;

        // Simple layer-based placement
        let mut current_x = margin;
        let mut current_y = margin;
        let mut current_z = margin;
        let mut row_depth = 0.0_f64;
        let mut layer_height = 0.0_f64;

        let mut total_placed_volume = 0.0;
        let mut total_placed_mass = 0.0;

        for geom in geometries {
            geom.validate()?;

            for instance in 0..geom.quantity() {
                if self.cancelled.load(Ordering::Relaxed) {
                    result.computation_time_ms = start.elapsed_ms();
                    return Ok(result);
                }

                // Check time limit (0 = unlimited)
                if self.config.time_limit_ms > 0 && start.elapsed_ms() >= self.config.time_limit_ms
                {
                    result.boundaries_used = if placements.is_empty() { 0 } else { 1 };
                    result.utilization = total_placed_volume / boundary.measure();
                    result.computation_time_ms = start.elapsed_ms();
                    result.placements = placements;
                    return Ok(result);
                }

                // Check mass constraint
                if let (Some(max_mass), Some(item_mass)) = (boundary.max_mass(), geom.mass()) {
                    if total_placed_mass + item_mass > max_mass {
                        result.unplaced.push(geom.id().clone());
                        continue;
                    }
                }

                // Try all allowed orientations to find the best fit
                let orientations = geom.allowed_orientations();
                let mut best_fit: BestFit3D = None;
                // (orientation_idx, width, depth, height, place_x, place_y, place_z, new_row_depth, new_layer_height)

                for (ori_idx, _) in orientations.iter().enumerate() {
                    let dims = geom.dimensions_for_orientation(ori_idx);
                    let g_width = dims.x;
                    let g_depth = dims.y;
                    let g_height = dims.z;

                    // Try current position first
                    let mut try_x = current_x;
                    let mut try_y = current_y;
                    let mut try_z = current_z;
                    let mut try_row_depth = row_depth;
                    let mut try_layer_height = layer_height;

                    // Check if fits in current row
                    if try_x + g_width > bound_max_x {
                        try_x = margin;
                        try_y += row_depth + spacing;
                        try_row_depth = 0.0;
                    }

                    // Check if fits in current layer
                    if try_y + g_depth > bound_max_y {
                        try_x = margin;
                        try_y = margin;
                        try_z += layer_height + spacing;
                        try_row_depth = 0.0;
                        try_layer_height = 0.0;
                    }

                    // Check if fits in container
                    if try_z + g_height > bound_max_z {
                        continue; // This orientation doesn't fit
                    }

                    // Score: prefer placements that use less vertical space (height)
                    // and stay in current row (lower y advancement)
                    let score = try_z * 1000000.0 + try_y * 1000.0 + try_x + g_height * 0.1;

                    let is_better = match &best_fit {
                        None => true,
                        Some((_, _, _, bg_height, bx, by, bz, _, _)) => {
                            let best_score = bz * 1000000.0 + by * 1000.0 + bx + bg_height * 0.1;
                            score < best_score
                        }
                    };

                    if is_better {
                        best_fit = Some((
                            ori_idx,
                            g_width,
                            g_depth,
                            g_height,
                            try_x,
                            try_y,
                            try_z,
                            try_row_depth,
                            try_layer_height,
                        ));
                    }
                }

                if let Some((
                    ori_idx,
                    g_width,
                    g_depth,
                    g_height,
                    place_x,
                    place_y,
                    place_z,
                    new_row_depth,
                    new_layer_height,
                )) = best_fit
                {
                    // Convert orientation index to rotation angles
                    // For simplicity, we encode orientation in rotation_index
                    let placement = Placement::new_3d(
                        geom.id().clone(),
                        instance,
                        place_x,
                        place_y,
                        place_z,
                        0.0, // Orientation is encoded via rotation_index
                        0.0,
                        0.0,
                    )
                    .with_rotation_index(ori_idx);

                    placements.push(placement);
                    total_placed_volume += geom.measure();
                    if let Some(mass) = geom.mass() {
                        total_placed_mass += mass;
                    }

                    // Update position for next item
                    current_x = place_x + g_width + spacing;
                    current_y = place_y;
                    current_z = place_z;
                    row_depth = new_row_depth.max(g_depth);
                    layer_height = new_layer_height.max(g_height);
                } else {
                    result.unplaced.push(geom.id().clone());
                }
            }
        }

        result.placements = placements;
        result.boundaries_used = 1;
        result.utilization = total_placed_volume / boundary.measure();
        result.computation_time_ms = start.elapsed_ms();

        Ok(result)
    }

    /// Genetic Algorithm based packing optimization.
    ///
    /// Uses GA to optimize placement order and orientations, with layer-based
    /// decoding for collision-free placements.
    fn genetic_algorithm(
        &self,
        geometries: &[Geometry3D],
        boundary: &Boundary3D,
    ) -> Result<SolveResult<f64>> {
        // Configure GA from solver config
        let ga_config = GaConfig::default()
            .with_population_size(self.config.population_size)
            .with_max_generations(self.config.max_generations)
            .with_crossover_rate(self.config.crossover_rate)
            .with_mutation_rate(self.config.mutation_rate);

        let result = run_ga_packing(
            geometries,
            boundary,
            &self.config,
            ga_config,
            self.cancelled.clone(),
        );

        Ok(result)
    }

    /// BRKGA (Biased Random-Key Genetic Algorithm) based packing optimization.
    ///
    /// Uses random-key encoding and biased crossover for robust optimization.
    fn brkga(&self, geometries: &[Geometry3D], boundary: &Boundary3D) -> Result<SolveResult<f64>> {
        // Configure BRKGA with reasonable defaults
        let brkga_config = BrkgaConfig::default()
            .with_population_size(50)
            .with_max_generations(100)
            .with_elite_fraction(0.2)
            .with_mutant_fraction(0.15)
            .with_elite_bias(0.7);

        let result = run_brkga_packing(
            geometries,
            boundary,
            &self.config,
            brkga_config,
            self.cancelled.clone(),
        );

        Ok(result)
    }

    /// Simulated Annealing based packing optimization.
    ///
    /// Uses neighborhood operators to explore solution space with temperature-based
    /// acceptance probability.
    fn simulated_annealing(
        &self,
        geometries: &[Geometry3D],
        boundary: &Boundary3D,
    ) -> Result<SolveResult<f64>> {
        // Configure SA with reasonable defaults
        let sa_config = SaConfig::default()
            .with_initial_temp(100.0)
            .with_final_temp(0.1)
            .with_cooling_rate(0.95)
            .with_iterations_per_temp(50)
            .with_max_iterations(10000);

        let result = run_sa_packing(
            geometries,
            boundary,
            &self.config,
            sa_config,
            self.cancelled.clone(),
        );

        Ok(result)
    }

    /// Extreme Point heuristic-based packing.
    ///
    /// Places boxes at extreme points (positions touching at least two surfaces).
    /// More efficient than layer-based packing for many scenarios.
    fn extreme_point(
        &self,
        geometries: &[Geometry3D],
        boundary: &Boundary3D,
    ) -> Result<SolveResult<f64>> {
        let start = Timer::now();

        let (ep_placements, utilization) = run_ep_packing(
            geometries,
            boundary,
            self.config.margin,
            self.config.spacing,
            boundary.max_mass(),
        );

        // Convert EP placements to Placement structs. The orientation index must be
        // preserved via `rotation_index` so the response can report the actual box
        // footprint; dropping it made every EP placement report the identity
        // orientation, which read as out-of-bounds for rotated boxes downstream.
        let mut placements = Vec::new();
        for (id, instance, position, orientation) in ep_placements {
            let placement = Placement::new_3d(
                id, instance, position.x, position.y, position.z, 0.0, // rotation_x
                0.0, // rotation_y
                0.0, // rotation_z (orientation encoded via rotation_index)
            )
            .with_rotation_index(orientation);
            placements.push(placement);
        }

        // Collect unplaced items
        let mut placed_ids: std::collections::HashSet<(String, usize)> =
            std::collections::HashSet::new();
        for p in &placements {
            placed_ids.insert((p.geometry_id.clone(), p.instance));
        }

        let mut unplaced = Vec::new();
        for geom in geometries {
            for instance in 0..geom.quantity() {
                if !placed_ids.contains(&(geom.id().clone(), instance)) {
                    unplaced.push(geom.id().clone());
                }
            }
        }

        let mut result = SolveResult::new();
        result.placements = placements;
        result.boundaries_used = 1;
        result.utilization = utilization;
        result.unplaced = unplaced;
        result.computation_time_ms = start.elapsed_ms();
        result.strategy = Some("ExtremePoint".to_string());

        Ok(result)
    }

    /// Layer packing with progress callback.
    fn layer_packing_with_progress(
        &self,
        geometries: &[Geometry3D],
        boundary: &Boundary3D,
        callback: &ProgressCallback,
    ) -> Result<SolveResult<f64>> {
        let start = Timer::now();
        let mut result = SolveResult::new();
        let mut placements = Vec::new();

        let margin = self.config.margin;
        let spacing = self.config.spacing;

        let bound_max_x = boundary.width() - margin;
        let bound_max_y = boundary.depth() - margin;
        let bound_max_z = boundary.height() - margin;

        let mut current_x = margin;
        let mut current_y = margin;
        let mut current_z = margin;
        let mut row_depth = 0.0_f64;
        let mut layer_height = 0.0_f64;

        let mut total_placed_volume = 0.0;
        let mut total_placed_mass = 0.0;

        // Count total pieces for progress
        let total_pieces: usize = geometries.iter().map(|g| g.quantity()).sum();
        let mut placed_count = 0usize;

        // Initial progress callback
        callback(
            ProgressInfo::new()
                .with_phase("Layer Packing")
                .with_items(0, total_pieces)
                .with_elapsed(0),
        );

        for geom in geometries {
            geom.validate()?;

            for instance in 0..geom.quantity() {
                if self.cancelled.load(Ordering::Relaxed) {
                    result.computation_time_ms = start.elapsed_ms();
                    callback(
                        ProgressInfo::new()
                            .with_phase("Cancelled")
                            .with_items(placed_count, total_pieces)
                            .with_elapsed(result.computation_time_ms)
                            .finished(),
                    );
                    return Ok(result);
                }

                // Check time limit (0 = unlimited)
                if self.config.time_limit_ms > 0 && start.elapsed_ms() >= self.config.time_limit_ms
                {
                    result.boundaries_used = if placements.is_empty() { 0 } else { 1 };
                    result.utilization = total_placed_volume / boundary.measure();
                    result.computation_time_ms = start.elapsed_ms();
                    result.placements = placements;
                    callback(
                        ProgressInfo::new()
                            .with_phase("Time Limit Reached")
                            .with_items(placed_count, total_pieces)
                            .with_elapsed(result.computation_time_ms)
                            .finished(),
                    );
                    return Ok(result);
                }

                // Check mass constraint
                if let (Some(max_mass), Some(item_mass)) = (boundary.max_mass(), geom.mass()) {
                    if total_placed_mass + item_mass > max_mass {
                        result.unplaced.push(geom.id().clone());
                        continue;
                    }
                }

                // Try all allowed orientations to find the best fit
                let orientations = geom.allowed_orientations();
                let mut best_fit: BestFit3D = None;

                for (ori_idx, _) in orientations.iter().enumerate() {
                    let dims = geom.dimensions_for_orientation(ori_idx);
                    let g_width = dims.x;
                    let g_depth = dims.y;
                    let g_height = dims.z;

                    let mut try_x = current_x;
                    let mut try_y = current_y;
                    let mut try_z = current_z;
                    let mut try_row_depth = row_depth;
                    let mut try_layer_height = layer_height;

                    if try_x + g_width > bound_max_x {
                        try_x = margin;
                        try_y += row_depth + spacing;
                        try_row_depth = 0.0;
                    }

                    if try_y + g_depth > bound_max_y {
                        try_x = margin;
                        try_y = margin;
                        try_z += layer_height + spacing;
                        try_row_depth = 0.0;
                        try_layer_height = 0.0;
                    }

                    if try_z + g_height > bound_max_z {
                        continue;
                    }

                    let score = try_z * 1000000.0 + try_y * 1000.0 + try_x + g_height * 0.1;

                    let is_better = match &best_fit {
                        None => true,
                        Some((_, _, _, bg_height, bx, by, bz, _, _)) => {
                            let best_score = bz * 1000000.0 + by * 1000.0 + bx + bg_height * 0.1;
                            score < best_score
                        }
                    };

                    if is_better {
                        best_fit = Some((
                            ori_idx,
                            g_width,
                            g_depth,
                            g_height,
                            try_x,
                            try_y,
                            try_z,
                            try_row_depth,
                            try_layer_height,
                        ));
                    }
                }

                if let Some((
                    ori_idx,
                    g_width,
                    g_depth,
                    g_height,
                    place_x,
                    place_y,
                    place_z,
                    new_row_depth,
                    new_layer_height,
                )) = best_fit
                {
                    let placement = Placement::new_3d(
                        geom.id().clone(),
                        instance,
                        place_x,
                        place_y,
                        place_z,
                        0.0,
                        0.0,
                        0.0,
                    )
                    .with_rotation_index(ori_idx);

                    placements.push(placement);
                    total_placed_volume += geom.measure();
                    if let Some(mass) = geom.mass() {
                        total_placed_mass += mass;
                    }
                    placed_count += 1;

                    current_x = place_x + g_width + spacing;
                    current_y = place_y;
                    current_z = place_z;
                    row_depth = new_row_depth.max(g_depth);
                    layer_height = new_layer_height.max(g_height);

                    // Progress callback every piece
                    callback(
                        ProgressInfo::new()
                            .with_phase("Layer Packing")
                            .with_items(placed_count, total_pieces)
                            .with_utilization(total_placed_volume / boundary.measure())
                            .with_elapsed(start.elapsed_ms()),
                    );
                } else {
                    result.unplaced.push(geom.id().clone());
                }
            }
        }

        result.placements = placements;
        result.boundaries_used = 1;
        result.utilization = total_placed_volume / boundary.measure();
        result.computation_time_ms = start.elapsed_ms();

        // Final progress callback
        callback(
            ProgressInfo::new()
                .with_phase("Complete")
                .with_items(placed_count, total_pieces)
                .with_utilization(result.utilization)
                .with_elapsed(result.computation_time_ms)
                .finished(),
        );

        Ok(result)
    }
}

impl Solver for Packer3D {
    type Geometry = Geometry3D;
    type Boundary = Boundary3D;
    type Scalar = f64;

    fn solve(
        &self,
        geometries: &[Self::Geometry],
        boundary: &Self::Boundary,
    ) -> Result<SolveResult<f64>> {
        boundary.validate()?;

        // Reset cancellation flag
        self.cancelled.store(false, Ordering::Relaxed);

        let mut result = match self.config.strategy {
            Strategy::BottomLeftFill => self.layer_packing(geometries, boundary),
            Strategy::ExtremePoint => self.extreme_point(geometries, boundary),
            Strategy::GeneticAlgorithm => self.genetic_algorithm(geometries, boundary),
            Strategy::Brkga => self.brkga(geometries, boundary),
            Strategy::SimulatedAnnealing => self.simulated_annealing(geometries, boundary),
            _ => {
                // Fall back to layer packing for unimplemented strategies
                log::warn!(
                    "Strategy {:?} not yet implemented, using layer packing",
                    self.config.strategy
                );
                self.layer_packing(geometries, boundary)
            }
        }?;

        // Remove duplicate entries from unplaced list
        result.deduplicate_unplaced();

        // Honor gravity/stability constraints, if requested, on the finished packing.
        if boundary.has_gravity() || boundary.has_stability() {
            self.enforce_support(&mut result, geometries, boundary);
        }
        Ok(result)
    }

    fn solve_with_progress(
        &self,
        geometries: &[Self::Geometry],
        boundary: &Self::Boundary,
        callback: ProgressCallback,
    ) -> Result<SolveResult<f64>> {
        boundary.validate()?;

        // Reset cancellation flag
        self.cancelled.store(false, Ordering::Relaxed);

        let mut result = match self.config.strategy {
            Strategy::BottomLeftFill => {
                self.layer_packing_with_progress(geometries, boundary, &callback)?
            }
            // EP is a fast single pass; run the real heuristic (not layer packing) and
            // skip incremental progress rather than silently substituting BLF.
            Strategy::ExtremePoint => self.extreme_point(geometries, boundary)?,
            // Other strategies fall back to basic progress reporting
            _ => {
                log::warn!(
                    "Strategy {:?} progress not yet implemented, using layer packing",
                    self.config.strategy
                );
                self.layer_packing_with_progress(geometries, boundary, &callback)?
            }
        };

        // Remove duplicate entries from unplaced list
        result.deduplicate_unplaced();

        // Honor gravity/stability constraints, if requested, on the finished packing.
        if boundary.has_gravity() || boundary.has_stability() {
            self.enforce_support(&mut result, geometries, boundary);
        }
        Ok(result)
    }

    fn cancel(&self) {
        self.cancelled.store(true, Ordering::Relaxed);
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_simple_packing() {
        let geometries = vec![
            Geometry3D::new("B1", 20.0, 20.0, 20.0).with_quantity(3),
            Geometry3D::new("B2", 15.0, 15.0, 15.0).with_quantity(2),
        ];

        let boundary = Boundary3D::new(100.0, 80.0, 50.0);
        let packer = Packer3D::default_config();

        let result = packer.solve(&geometries, &boundary).unwrap();

        assert!(result.utilization > 0.0);
        assert!(result.placements.len() <= 5);
    }

    #[test]
    fn test_mass_constraint() {
        let geometries = vec![Geometry3D::new("B1", 20.0, 20.0, 20.0)
            .with_quantity(10)
            .with_mass(100.0)];

        let boundary = Boundary3D::new(100.0, 80.0, 50.0).with_max_mass(350.0);

        let packer = Packer3D::default_config();
        let result = packer.solve(&geometries, &boundary).unwrap();

        // Should only place 3 boxes (300 mass) due to 350 mass limit
        assert!(result.placements.len() <= 3);
    }

    #[test]
    fn test_placement_within_bounds() {
        let geometries = vec![Geometry3D::new("B1", 10.0, 10.0, 10.0).with_quantity(4)];

        let boundary = Boundary3D::new(50.0, 50.0, 50.0);
        let config = Config::default().with_margin(5.0).with_spacing(2.0);
        let packer = Packer3D::new(config);

        let result = packer.solve(&geometries, &boundary).unwrap();

        // All boxes should be placed
        assert_eq!(result.placements.len(), 4);
        assert!(result.unplaced.is_empty());

        // Verify placements are within bounds (with margin)
        for p in &result.placements {
            assert!(p.position[0] >= 5.0);
            assert!(p.position[1] >= 5.0);
            assert!(p.position[2] >= 5.0);
        }
    }

    #[test]
    fn test_ga_strategy_basic() {
        let geometries = vec![
            Geometry3D::new("B1", 20.0, 20.0, 20.0).with_quantity(2),
            Geometry3D::new("B2", 15.0, 15.0, 15.0).with_quantity(2),
        ];

        let boundary = Boundary3D::new(100.0, 80.0, 50.0);
        let config = Config::default().with_strategy(Strategy::GeneticAlgorithm);
        let packer = Packer3D::new(config);

        let result = packer.solve(&geometries, &boundary).unwrap();

        // GA should place items and achieve positive utilization
        assert!(result.utilization > 0.0);
        assert!(!result.placements.is_empty());
    }

    #[test]
    fn test_ga_strategy_all_placed() {
        // Small number of boxes that should all fit
        let geometries = vec![Geometry3D::new("B1", 10.0, 10.0, 10.0).with_quantity(4)];

        let boundary = Boundary3D::new(100.0, 100.0, 100.0);
        let config = Config::default().with_strategy(Strategy::GeneticAlgorithm);
        let packer = Packer3D::new(config);

        let result = packer.solve(&geometries, &boundary).unwrap();

        // All 4 boxes should be placed
        assert_eq!(result.placements.len(), 4);
        assert!(result.unplaced.is_empty());
    }

    #[test]
    #[cfg(feature = "serde")]
    fn test_3d_response_orientation_in_bounds() {
        use crate::build_pack3d_response;
        use crate::geometry::OrientationConstraint;

        // A tall box in a flat container can only be placed rotated. The response must
        // report the orientation that was actually used, so reconstructing the box
        // footprint from the reported orientation label keeps it inside the boundary.
        // Pre-fix, EP/GA/BRKGA dropped the orientation and reported "xyz" (identity),
        // making rotated placements read as out-of-bounds (the 0.3.3 "oob" reports).
        let (bw, bd, bh) = (100.0_f64, 100.0_f64, 30.0_f64);
        let boundary = Boundary3D::new(bw, bd, bh);

        for strategy in [
            Strategy::ExtremePoint,
            Strategy::GeneticAlgorithm,
            Strategy::Brkga,
        ] {
            let geometries = vec![Geometry3D::new("tall", 25.0, 25.0, 80.0)
                .with_quantity(3)
                .with_orientation(OrientationConstraint::Any)];
            let config = Config::default().with_strategy(strategy);
            let packer = Packer3D::new(config);
            let result = packer.solve(&geometries, &boundary).unwrap();
            let response = build_pack3d_response(&result, &geometries);

            // EP is deterministic and must place at least one box (only fits rotated).
            if strategy == Strategy::ExtremePoint {
                assert!(
                    !response.placements.is_empty(),
                    "EP should place the tall box by rotating it into the flat container"
                );
            }

            let base = geometries[0].dimensions_for_orientation(0); // unrotated dims
            for p in &response.placements {
                let axes: Vec<usize> = p
                    .orientation
                    .chars()
                    .map(|c| match c {
                        'x' => 0,
                        'y' => 1,
                        'z' => 2,
                        _ => panic!("unexpected orientation label '{}'", p.orientation),
                    })
                    .collect();
                let (dx, dy, dz) = (base[axes[0]], base[axes[1]], base[axes[2]]);
                let e = 1e-6;
                assert!(
                    p.x + dx <= bw + e && p.y + dy <= bd + e && p.z + dz <= bh + e,
                    "{:?} {}#{} out of bounds for reported orientation '{}': \
                     pos({:.1},{:.1},{:.1}) dims({dx:.1},{dy:.1},{dz:.1}) boundary({bw},{bd},{bh})",
                    strategy,
                    p.geometry_id,
                    p.instance,
                    p.orientation,
                    p.x,
                    p.y,
                    p.z,
                );
            }
        }
    }

    #[test]
    fn test_ga_strategy_with_orientations() {
        use crate::geometry::OrientationConstraint;

        // Box that fits better when rotated
        let geometries = vec![Geometry3D::new("B1", 50.0, 10.0, 10.0)
            .with_quantity(2)
            .with_orientation(OrientationConstraint::Any)];

        // Container where orientation matters
        let boundary = Boundary3D::new(60.0, 60.0, 60.0);
        let config = Config::default().with_strategy(Strategy::GeneticAlgorithm);
        let packer = Packer3D::new(config);

        let result = packer.solve(&geometries, &boundary).unwrap();

        // GA should find a way to place both boxes
        assert_eq!(result.placements.len(), 2);
    }

    #[test]
    fn test_brkga_strategy_basic() {
        let geometries = vec![
            Geometry3D::new("B1", 20.0, 20.0, 20.0).with_quantity(2),
            Geometry3D::new("B2", 15.0, 15.0, 15.0).with_quantity(2),
        ];

        let boundary = Boundary3D::new(100.0, 80.0, 50.0);
        let config = Config::default().with_strategy(Strategy::Brkga);
        let packer = Packer3D::new(config);

        let result = packer.solve(&geometries, &boundary).unwrap();

        // BRKGA should place items and achieve positive utilization
        assert!(result.utilization > 0.0);
        assert!(!result.placements.is_empty());
        assert_eq!(result.strategy, Some("BRKGA".to_string()));
    }

    #[test]
    fn test_brkga_strategy_all_placed() {
        // Small number of boxes that should all fit
        let geometries = vec![Geometry3D::new("B1", 10.0, 10.0, 10.0).with_quantity(4)];

        let boundary = Boundary3D::new(100.0, 100.0, 100.0);
        let config = Config::default().with_strategy(Strategy::Brkga);
        let packer = Packer3D::new(config);

        let result = packer.solve(&geometries, &boundary).unwrap();

        // All 4 boxes should be placed
        assert_eq!(result.placements.len(), 4);
        assert!(result.unplaced.is_empty());
    }

    #[test]
    fn test_ep_strategy_basic() {
        let geometries = vec![
            Geometry3D::new("B1", 20.0, 20.0, 20.0).with_quantity(2),
            Geometry3D::new("B2", 15.0, 15.0, 15.0).with_quantity(2),
        ];

        let boundary = Boundary3D::new(100.0, 80.0, 50.0);
        let config = Config::default().with_strategy(Strategy::ExtremePoint);
        let packer = Packer3D::new(config);

        let result = packer.solve(&geometries, &boundary).unwrap();

        // EP should place items and achieve positive utilization
        assert!(result.utilization > 0.0);
        assert!(!result.placements.is_empty());
        assert_eq!(result.strategy, Some("ExtremePoint".to_string()));
    }

    #[test]
    fn test_ep_strategy_all_placed() {
        // Small number of boxes that should all fit
        let geometries = vec![Geometry3D::new("B1", 10.0, 10.0, 10.0).with_quantity(4)];

        let boundary = Boundary3D::new(100.0, 100.0, 100.0);
        let config = Config::default().with_strategy(Strategy::ExtremePoint);
        let packer = Packer3D::new(config);

        let result = packer.solve(&geometries, &boundary).unwrap();

        // All 4 boxes should be placed
        assert_eq!(result.placements.len(), 4);
        assert!(result.unplaced.is_empty());
    }

    #[test]
    fn test_ep_strategy_with_margin() {
        let geometries = vec![Geometry3D::new("B1", 20.0, 20.0, 20.0).with_quantity(4)];

        let boundary = Boundary3D::new(100.0, 100.0, 100.0);
        let config = Config::default()
            .with_strategy(Strategy::ExtremePoint)
            .with_margin(5.0);
        let packer = Packer3D::new(config);

        let result = packer.solve(&geometries, &boundary).unwrap();

        // Verify placements start at margin
        for p in &result.placements {
            assert!(p.position[0] >= 4.9);
            assert!(p.position[1] >= 4.9);
            assert!(p.position[2] >= 4.9);
        }
    }

    #[test]
    fn test_ep_strategy_with_orientations() {
        use crate::geometry::OrientationConstraint;

        // Long box that benefits from rotation
        let geometries = vec![Geometry3D::new("B1", 80.0, 10.0, 10.0)
            .with_quantity(2)
            .with_orientation(OrientationConstraint::Any)];

        let boundary = Boundary3D::new(100.0, 100.0, 100.0);
        let config = Config::default().with_strategy(Strategy::ExtremePoint);
        let packer = Packer3D::new(config);

        let result = packer.solve(&geometries, &boundary).unwrap();

        // EP should find a way to place both boxes
        assert_eq!(result.placements.len(), 2);
    }

    #[test]
    fn test_ep_strategy_perfect_fill_via_solve() {
        // End-to-end through Packer3D::solve (the path FFI/WASM use): eight 50-cubes
        // tile a 100^3 container exactly. EP must place all 8. Guards the under-packing
        // regression at the dispatch level, not just run_ep_packing.
        let geometries = vec![Geometry3D::new("cube", 50.0, 50.0, 50.0).with_quantity(8)];
        let boundary = Boundary3D::new(100.0, 100.0, 100.0);
        let packer = Packer3D::new(Config::default().with_strategy(Strategy::ExtremePoint));

        let result = packer.solve(&geometries, &boundary).unwrap();

        assert_eq!(result.placements.len(), 8, "EP must place all 8 cubes");
        assert!(result.unplaced.is_empty());
    }

    #[test]
    fn test_ep_at_least_as_good_as_blf() {
        // A correct Extreme-Point heuristic never places fewer boxes than the simpler
        // layer (BLF) strategy on the same instance. Before the fix EP stalled far below
        // BLF (e.g. 4 vs 13 on the mixed-box set). Covers several shapes.
        let boundary = Boundary3D::new(85.0, 85.0, 80.0);
        let cases: [(&str, f64, f64, f64, usize); 3] = [
            ("big", 40.0, 40.0, 40.0, 4),
            ("mid", 30.0, 20.0, 25.0, 6),
            ("small", 15.0, 15.0, 30.0, 8),
        ];
        let geometries: Vec<Geometry3D> = cases
            .iter()
            .map(|(id, w, d, h, q)| Geometry3D::new(*id, *w, *d, *h).with_quantity(*q))
            .collect();

        let blf = Packer3D::new(Config::default().with_strategy(Strategy::BottomLeftFill))
            .solve(&geometries, &boundary)
            .unwrap();
        let ep = Packer3D::new(Config::default().with_strategy(Strategy::ExtremePoint))
            .solve(&geometries, &boundary)
            .unwrap();

        assert!(
            ep.placements.len() >= blf.placements.len(),
            "EP placed {} but BLF placed {} — EP must not regress below BLF",
            ep.placements.len(),
            blf.placements.len()
        );
    }

    /// Builds a result whose second box floats above the floor with nothing beneath it.
    fn floating_pair() -> (Vec<Geometry3D>, SolveResult<f64>) {
        let geometries = vec![
            Geometry3D::new("a", 20.0, 20.0, 20.0),
            Geometry3D::new("b", 20.0, 20.0, 20.0),
        ];
        let mut result = SolveResult::new();
        result.placements.push(
            Placement::new_3d("a".to_string(), 0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0)
                .with_rotation_index(0),
        );
        // "b" hovers at z=50 — no floor contact, no box below.
        result.placements.push(
            Placement::new_3d("b".to_string(), 0, 0.0, 0.0, 50.0, 0.0, 0.0, 0.0)
                .with_rotation_index(0),
        );
        (geometries, result)
    }

    #[test]
    fn test_gravity_removes_floating_box() {
        let (geometries, mut result) = floating_pair();
        let boundary = Boundary3D::new(100.0, 100.0, 100.0).with_gravity(true);
        let packer = Packer3D::default_config();

        packer.enforce_support(&mut result, &geometries, &boundary);

        let ids: Vec<&str> = result
            .placements
            .iter()
            .map(|p| p.geometry_id.as_str())
            .collect();
        assert_eq!(ids, vec!["a"], "floating box must be dropped under gravity");
        assert!(result.unplaced.iter().any(|id| id == "b"));
    }

    #[test]
    fn test_no_constraint_keeps_floating_box() {
        // Without gravity/stability the solver never calls enforce_support, so a result
        // with a floating box is returned untouched. Verify enforce_support is the only
        // thing that would remove it — i.e. solve() leaves such input alone.
        let (geometries, result) = floating_pair();
        let boundary = Boundary3D::new(100.0, 100.0, 100.0);
        assert!(!boundary.has_gravity() && !boundary.has_stability());
        // The pair was hand-built (not via solve); just assert the boundary flags gate it.
        assert_eq!(result.placements.len(), 2);
        let _ = geometries;
    }

    #[test]
    fn test_gravity_keeps_floor_boxes_with_margin() {
        // With a wall margin the pack starts boxes at z = margin, which the support
        // analysis must treat as the floor. If it checks against z = 0 instead, every
        // bottom-layer box reads as floating and the whole pack gets dropped. End-to-end
        // through solve() with margin > 0 and gravity on.
        let geometries = vec![
            Geometry3D::new("big", 40.0, 40.0, 40.0).with_quantity(4),
            Geometry3D::new("mid", 30.0, 20.0, 25.0).with_quantity(6),
        ];
        let boundary = Boundary3D::new(100.0, 100.0, 100.0).with_gravity(true);
        let packer = Packer3D::new(
            Config::default()
                .with_margin(5.0)
                .with_strategy(Strategy::BottomLeftFill),
        );

        let result = packer.solve(&geometries, &boundary).unwrap();

        assert!(
            !result.placements.is_empty(),
            "margin>0 + gravity must not drop floor-resting boxes"
        );
    }

    #[test]
    fn test_stability_drops_undersupported_box() {
        // "b" rests on "a" but overlaps only a thin sliver of its top face (well under
        // the 70% base-support threshold). Gravity alone keeps it (it does touch below);
        // stability drops it.
        let geometries = vec![
            Geometry3D::new("a", 40.0, 40.0, 20.0),
            Geometry3D::new("b", 40.0, 40.0, 20.0),
        ];
        let make = || {
            let mut r = SolveResult::new();
            r.placements.push(
                Placement::new_3d("a".to_string(), 0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0)
                    .with_rotation_index(0),
            );
            // shifted so only a 5x40 strip (≈12.5%) of b's base sits on a's top
            r.placements.push(
                Placement::new_3d("b".to_string(), 0, 35.0, 0.0, 20.0, 0.0, 0.0, 0.0)
                    .with_rotation_index(0),
            );
            r
        };
        let packer = Packer3D::default_config();

        let mut grav = make();
        packer.enforce_support(
            &mut grav,
            &geometries,
            &Boundary3D::new(100.0, 100.0, 100.0).with_gravity(true),
        );
        assert_eq!(
            grav.placements.len(),
            2,
            "gravity keeps a box that touches below"
        );

        let mut stab = make();
        packer.enforce_support(
            &mut stab,
            &geometries,
            &Boundary3D::new(100.0, 100.0, 100.0).with_stability(true),
        );
        assert!(
            stab.placements.iter().all(|p| p.geometry_id == "a"),
            "stability drops the under-supported box"
        );
    }

    #[test]
    fn test_layer_packing_orientation_optimization() {
        use crate::geometry::OrientationConstraint;

        // A box 50x10x10 that won't fit in 45 width without rotation
        // But at orientation (1,0,2) it becomes 10x50x10, width=10, which fits
        let geometries = vec![Geometry3D::new("B1", 50.0, 10.0, 10.0)
            .with_quantity(2)
            .with_orientation(OrientationConstraint::Any)];

        // Narrow container: width=45, depth=80, height=80
        let boundary = Boundary3D::new(45.0, 80.0, 80.0);
        let config = Config::default().with_strategy(Strategy::BottomLeftFill);
        let packer = Packer3D::new(config);

        let result = packer.solve(&geometries, &boundary).unwrap();

        // Both boxes should be placed via orientation change
        assert_eq!(
            result.placements.len(),
            2,
            "Both boxes should be placed by using rotation"
        );
        assert!(result.unplaced.is_empty());

        // Verify orientation index is set for placements
        for p in &result.placements {
            assert!(
                p.rotation_index.is_some(),
                "Placement should have rotation_index set"
            );
        }
    }

    #[test]
    fn test_layer_packing_selects_best_orientation() {
        use crate::geometry::OrientationConstraint;

        // Box 30x20x10 in container 35x50x100
        // Original orientation (30x20x10): fits in row, leaves 5 spare width
        // Rotated (20x30x10): fits but uses more depth
        // Best: original orientation to minimize vertical space usage
        let geometries = vec![Geometry3D::new("B1", 30.0, 20.0, 10.0)
            .with_quantity(1)
            .with_orientation(OrientationConstraint::Any)];

        let boundary = Boundary3D::new(35.0, 50.0, 100.0);
        let packer = Packer3D::default_config();

        let result = packer.solve(&geometries, &boundary).unwrap();

        assert_eq!(result.placements.len(), 1);
        assert!(result.unplaced.is_empty());
    }
}