u-nesting-d2 0.7.2

//! Integration tests for u-nesting-d2.

use u_nesting_d2::{
    Boundary, Boundary2D, Config, Geometry, Geometry2D, Geometry2DExt, Nester2D, Solver, Strategy,
    Transform2D, AABB2D,
};

mod geometry_tests {
    use super::*;

    #[test]
    fn test_rectangle_geometry() {
        let rect = Geometry2D::rectangle("rect1", 20.0, 15.0);

        // Area should be width * height
        let area = rect.measure();
        assert!((area - 300.0).abs() < 0.001);

        // Perimeter should be 2*(w+h)
        let perim = rect.perimeter();
        assert!((perim - 70.0).abs() < 0.001);

        // Rectangle should be convex
        assert!(rect.is_convex());

        // Vertices should form a rectangle
        let vertices = rect.outer_ring();
        assert_eq!(vertices.len(), 4);
    }

    #[test]
    fn test_circle_approximation() {
        let circle = Geometry2D::circle("circle1", 10.0, 64);

        // Area should be approximately π*r²
        let expected_area = std::f64::consts::PI * 10.0 * 10.0;
        let actual_area = circle.measure();
        assert!(
            (actual_area - expected_area).abs() < 3.0,
            "Circle area {} should be close to {}",
            actual_area,
            expected_area
        );

        // Circle approximation should be convex
        assert!(circle.is_convex());

        // Should have 64 vertices
        assert_eq!(circle.outer_ring().len(), 64);
    }

    #[test]
    fn test_l_shape_non_convex() {
        let l_shape = Geometry2D::l_shape("l1", 30.0, 30.0, 15.0, 15.0);

        // L-shape should NOT be convex
        assert!(!l_shape.is_convex());

        // Area calculation: 30*30 - 15*15 = 900 - 225 = 675
        // Wait, L-shape is: total width=30, height=30, notch width=15, notch height=15
        // Vertices: (0,0), (30,0), (30,15), (15,15), (15,30), (0,30)
        // Area: 30*30 - 15*15 = 675? No, let's compute correctly:
        // The L has a notch cut out of the top-right
        // Actually the l_shape creates:
        // (0,0), (width,0), (width,notch_height), (notch_width,notch_height), (notch_width,height), (0,height)
        // So it's: 30*15 + 15*30 = 450 + 450 = 900 - overlap = ...
        // Let's just verify it's positive and reasonable
        let area = l_shape.measure();
        assert!(area > 0.0);
        assert!(area < 900.0); // Less than bounding rectangle

        // Convex hull should be the bounding rectangle
        let hull = l_shape.convex_hull();
        assert!(hull.len() >= 4);
    }

    #[test]
    fn test_geometry_with_hole() {
        let poly_with_hole = Geometry2D::new("frame")
            .with_polygon(vec![(0.0, 0.0), (100.0, 0.0), (100.0, 100.0), (0.0, 100.0)])
            .with_hole(vec![(25.0, 25.0), (75.0, 25.0), (75.0, 75.0), (25.0, 75.0)]);

        // Area should be outer - hole = 10000 - 2500 = 7500
        let area = poly_with_hole.measure();
        assert!((area - 7500.0).abs() < 0.001, "Area = {}", area);

        // Not convex due to hole
        assert!(!poly_with_hole.is_convex());
    }

    #[test]
    fn test_geometry_aabb() {
        let geom = Geometry2D::new("offset_rect").with_polygon(vec![
            (10.0, 20.0),
            (50.0, 20.0),
            (50.0, 60.0),
            (10.0, 60.0),
        ]);

        let aabb = geom.aabb_2d();
        assert!((aabb.min_x - 10.0).abs() < 1e-10);
        assert!((aabb.min_y - 20.0).abs() < 1e-10);
        assert!((aabb.max_x - 50.0).abs() < 1e-10);
        assert!((aabb.max_y - 60.0).abs() < 1e-10);
        assert!((aabb.width() - 40.0).abs() < 1e-10);
        assert!((aabb.height() - 40.0).abs() < 1e-10);
    }

    #[test]
    fn test_geometry_centroid() {
        let rect = Geometry2D::rectangle("centered", 10.0, 10.0);
        let centroid = rect.centroid();

        assert!((centroid[0] - 5.0).abs() < 0.001);
        assert!((centroid[1] - 5.0).abs() < 0.001);
    }

    #[test]
    fn test_geometry_validation() {
        // Valid geometry
        let valid = Geometry2D::rectangle("valid", 10.0, 10.0);
        assert!(valid.validate().is_ok());

        // Invalid: less than 3 vertices
        let invalid = Geometry2D::new("invalid").with_polygon(vec![(0.0, 0.0), (1.0, 0.0)]);
        assert!(invalid.validate().is_err());

        // Invalid: zero quantity
        let zero_qty = Geometry2D::rectangle("zero", 10.0, 10.0).with_quantity(0);
        assert!(zero_qty.validate().is_err());
    }

    #[test]
    fn test_geometry_rotations() {
        let geom = Geometry2D::rectangle("rot", 10.0, 10.0)
            .with_rotations_deg(vec![0.0, 90.0, 180.0, 270.0]);

        let rotations = geom.rotations();
        assert_eq!(rotations.len(), 4);

        let pi = std::f64::consts::PI;
        assert!((rotations[0] - 0.0).abs() < 1e-10);
        assert!((rotations[1] - pi / 2.0).abs() < 1e-10);
        assert!((rotations[2] - pi).abs() < 1e-10);
        assert!((rotations[3] - 3.0 * pi / 2.0).abs() < 1e-10);
    }
}

mod boundary_tests {
    use super::*;
    use u_nesting_d2::Boundary2DExt;

    #[test]
    fn test_rectangle_boundary() {
        let boundary = Boundary2D::rectangle(200.0, 100.0);

        assert_eq!(boundary.width(), Some(200.0));
        assert_eq!(boundary.height(), Some(100.0));
        assert!(!boundary.is_infinite());

        let area = boundary.measure();
        assert!((area - 20000.0).abs() < 0.001);
    }

    #[test]
    fn test_strip_boundary() {
        let strip = Boundary2D::strip(100.0);

        assert_eq!(strip.width(), Some(100.0));
        assert_eq!(strip.height(), None);
        assert!(strip.is_infinite());

        let area = strip.measure();
        assert!(area == f64::INFINITY);
    }

    #[test]
    fn test_boundary_with_hole() {
        let boundary = Boundary2D::rectangle(100.0, 100.0).with_hole(vec![
            (40.0, 40.0),
            (60.0, 40.0),
            (60.0, 60.0),
            (40.0, 60.0),
        ]);

        // Area should be reduced by the hole
        let area = boundary.measure();
        // 10000 - 400 = 9600
        assert!((area - 9600.0).abs() < 0.001, "Area = {}", area);
    }

    #[test]
    fn test_boundary_contains_point() {
        let boundary = Boundary2D::rectangle(100.0, 100.0);

        // Point inside
        assert!(boundary.contains_point(&[50.0, 50.0]));

        // Point outside
        assert!(!boundary.contains_point(&[150.0, 50.0]));
        assert!(!boundary.contains_point(&[-10.0, 50.0]));

        // Point on edge (behavior may vary)
        // Just test points clearly inside/outside
    }

    #[test]
    fn test_boundary_aabb() {
        let boundary = Boundary2D::rectangle(150.0, 75.0);
        let aabb = boundary.aabb_2d();

        assert!((aabb.min_x - 0.0).abs() < 1e-10);
        assert!((aabb.min_y - 0.0).abs() < 1e-10);
        assert!((aabb.max_x - 150.0).abs() < 1e-10);
        assert!((aabb.max_y - 75.0).abs() < 1e-10);
    }

    #[test]
    fn test_boundary_effective_area() {
        let boundary = Boundary2D::rectangle(100.0, 100.0);

        // With margin of 10, effective dimensions are 80x80
        let effective = boundary.effective_area(10.0);
        assert!((effective - 6400.0).abs() < 0.001);

        // With margin of 0
        let full = boundary.effective_area(0.0);
        assert!((full - 10000.0).abs() < 0.001);
    }

    #[test]
    fn test_boundary_validation() {
        // Valid boundary
        let valid = Boundary2D::rectangle(100.0, 50.0);
        assert!(valid.validate().is_ok());

        // Invalid: less than 3 vertices
        let invalid = Boundary2D::new(vec![(0.0, 0.0), (1.0, 0.0)]);
        assert!(invalid.validate().is_err());
    }
}

mod nester_tests {
    use super::*;

    #[test]
    fn test_simple_rectangle_nesting() {
        let geometries = vec![Geometry2D::rectangle("A", 10.0, 10.0).with_quantity(4)];
        let boundary = Boundary2D::rectangle(100.0, 50.0);

        let nester = Nester2D::default_config();
        let result = nester.solve(&geometries, &boundary).unwrap();

        // All 4 pieces should be placed (boundary is large enough)
        assert_eq!(result.placements.len(), 4);
        assert!(result.unplaced.is_empty());
        assert!(result.utilization > 0.0);
    }

    #[test]
    fn test_mixed_geometry_nesting() {
        let geometries = vec![
            Geometry2D::rectangle("large", 30.0, 20.0).with_quantity(2),
            Geometry2D::rectangle("small", 10.0, 10.0).with_quantity(5),
        ];
        let boundary = Boundary2D::rectangle(200.0, 100.0);

        let nester = Nester2D::default_config();
        let result = nester.solve(&geometries, &boundary).unwrap();

        // All pieces should fit
        assert_eq!(result.placements.len(), 7); // 2 + 5
        assert!(result.boundaries_used == 1);
    }

    #[test]
    fn test_nesting_with_margin_and_spacing() {
        let geometries = vec![Geometry2D::rectangle("piece", 20.0, 20.0).with_quantity(4)];
        let boundary = Boundary2D::rectangle(100.0, 100.0);

        let config = Config::default().with_margin(10.0).with_spacing(5.0);
        let nester = Nester2D::new(config);

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

        // With margin=10, usable area is 80x80
        // With spacing=5, pieces of 20x20 should fit
        // First row: 20 + 5 + 20 + 5 + 20 = 70 < 80, so 3 can fit in a row
        // Second row: 1 more piece
        assert_eq!(result.placements.len(), 4);
    }

    #[test]
    fn test_nesting_overflow() {
        let geometries = vec![Geometry2D::rectangle("big", 60.0, 60.0).with_quantity(5)];
        let boundary = Boundary2D::rectangle(100.0, 100.0);

        let nester = Nester2D::default_config();
        let result = nester.solve(&geometries, &boundary).unwrap();

        // Only 1 piece can fit in a 100x100 boundary
        assert_eq!(result.placements.len(), 1);
        // `unplaced` is deduplicated to unique geometry IDs, so its length is 1
        // even though 4 of the 5 requested instances failed to place.
        assert_eq!(result.unplaced.len(), 1);
        // `total_requested` is instance-level (Σ quantity), so the true number of
        // unplaced instances is recoverable as total_requested - placements.len().
        assert_eq!(result.total_requested, 5);
        assert_eq!(
            result.total_requested - result.placements.len(),
            4,
            "4 of 5 instances should be unplaced"
        );
    }

    #[test]
    fn test_utilization_calculation() {
        let geometries = vec![Geometry2D::rectangle("quarter", 50.0, 50.0).with_quantity(1)];
        let boundary = Boundary2D::rectangle(100.0, 100.0);

        let nester = Nester2D::default_config();
        let result = nester.solve(&geometries, &boundary).unwrap();

        // 1 piece of 2500 in area of 10000 = 25% utilization
        assert!(
            (result.utilization - 0.25).abs() < 0.01,
            "Utilization = {}",
            result.utilization
        );
    }
}

/// Regression tests for the metaheuristic-quality fixes (ISSUE-u-nesting
/// -20260714-metaheuristic-quality): seed reproducibility and the guarantee
/// that GA/BRKGA/SA never return a solution worse than the BLF baseline.
mod metaheuristic_quality_tests {
    use super::*;

    fn instance() -> (Vec<Geometry2D>, Boundary2D) {
        let geometries = vec![Geometry2D::rectangle("p", 300.0, 200.0).with_quantity(10)];
        let boundary = Boundary2D::rectangle(1000.0, 5000.0);
        (geometries, boundary)
    }

    #[test]
    fn ga_is_reproducible_with_seed() {
        let (geometries, boundary) = instance();
        let config = Config::default()
            .with_strategy(Strategy::GeneticAlgorithm)
            .with_time_limit(1500)
            .with_seed(42);

        let a = Nester2D::new(config.clone())
            .solve(&geometries, &boundary)
            .unwrap();
        let b = Nester2D::new(config).solve(&geometries, &boundary).unwrap();

        // Same seed must yield an identical placement set.
        assert_eq!(a.placements.len(), b.placements.len());
        for (pa, pb) in a.placements.iter().zip(b.placements.iter()) {
            assert_eq!(pa.geometry_id, pb.geometry_id);
            assert_eq!(pa.position, pb.position);
            assert_eq!(pa.rotation, pb.rotation);
        }
    }

    /// The stochastic strategies must never pack worse than plain BLF; the
    /// `not_worse_than_blf` guard falls back to the greedy solution otherwise.
    #[test]
    fn metaheuristics_are_never_worse_than_blf() {
        let (geometries, boundary) = instance();

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

        for strategy in [
            Strategy::GeneticAlgorithm,
            Strategy::Brkga,
            Strategy::SimulatedAnnealing,
        ] {
            let config = Config::default()
                .with_strategy(strategy)
                .with_time_limit(1500)
                .with_seed(7);
            let result = Nester2D::new(config).solve(&geometries, &boundary).unwrap();

            // Never place fewer pieces than the greedy baseline.
            assert!(
                result.placements.len() >= blf.placements.len(),
                "{strategy:?} placed {} < BLF {}",
                result.placements.len(),
                blf.placements.len()
            );
        }
    }

    /// The callback-driven entry point (`solve_with_progress`, used by the FFI
    /// `solve_2d_with_callback` and the WASM/demo path) must apply the same BLF
    /// floor as `solve`. Without the guard on that dispatch site, a GA run worse
    /// than BLF would slip through only when a progress callback is supplied.
    #[test]
    fn progress_ga_is_never_worse_than_blf() {
        let (geometries, boundary) = instance();

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

        let config = Config::default()
            .with_strategy(Strategy::GeneticAlgorithm)
            .with_time_limit(1500);
        let result = Nester2D::new(config)
            .solve_with_progress(&geometries, &boundary, Box::new(|_| {}))
            .unwrap();

        assert!(
            result.placements.len() >= blf.placements.len(),
            "progress GA placed {} < BLF {}",
            result.placements.len(),
            blf.placements.len()
        );
    }

    // ---- rotation handling (issue #3 재현 B) -------------------------------
    //
    // An L-shaped (concave) piece on a tall open-roll strip. This is the shape
    // and geometry where the GA decoder previously *worsened* the layout as the
    // rotation set grew (used length 306 -> 752 -> 812) and where the old
    // bounding-box-area floor let that regression through: a taller, narrower
    // column has a smaller area yet a longer strip. The floor now compares strip
    // length, so the regression is caught.

    fn l_instance(rotations: Vec<f64>) -> (Vec<Geometry2D>, Boundary2D) {
        let l = Geometry2D::new("L")
            .with_polygon(vec![
                (0.0, 0.0),
                (100.0, 0.0),
                (100.0, 40.0),
                (40.0, 40.0),
                (40.0, 100.0),
                (0.0, 100.0),
            ])
            .with_quantity(8)
            .with_rotations_deg(rotations);
        (vec![l], Boundary2D::rectangle(300.0, 5000.0))
    }

    /// Strip length = extent along the boundary's open (Y) axis for the tall
    /// roll used here — the material consumed, which is what the layout minimizes.
    fn strip_length(result: &u_nesting_d2::SolveResult<f64>, geoms: &[Geometry2D]) -> f64 {
        let (mut min_y, mut max_y) = (f64::INFINITY, f64::NEG_INFINITY);
        for p in &result.placements {
            let g = geoms.iter().find(|g| g.id() == &p.geometry_id).unwrap();
            let rot = p.rotation.first().copied().unwrap_or(0.0);
            let (g_min, g_max) = g.aabb_at_rotation(rot);
            min_y = min_y.min(p.position[1] + g_min[1]);
            max_y = max_y.max(p.position[1] + g_max[1]);
        }
        if result.placements.is_empty() {
            0.0
        } else {
            max_y - min_y
        }
    }

    fn solve(strategy: Strategy, rotations: Vec<f64>) -> (Vec<Geometry2D>, f64) {
        let (geoms, boundary) = l_instance(rotations);
        // A short budget is enough: `not_worse_than_blf` always computes BLF and
        // floors the stochastic result to it, so the outcome is deterministic in
        // the strip-length metric regardless of how far GA/BRKGA converge.
        let config = Config::default()
            .with_strategy(strategy)
            .with_spacing(2.0)
            .with_seed(42)
            .with_time_limit(800);
        let r = Nester2D::new(config).solve(&geoms, &boundary).unwrap();
        let len = strip_length(&r, &geoms);
        (geoms, len)
    }

    /// The stochastic strategies must never consume a longer strip than plain
    /// BLF. This is the corrected floor's real guarantee — the old area-based
    /// floor missed the tall-narrow regression entirely.
    #[test]
    fn metaheuristics_never_exceed_blf_strip_length() {
        let rots = vec![0.0, 90.0, 180.0, 270.0];
        let (geoms, blf_len) = solve(Strategy::BottomLeftFill, rots.clone());
        for strat in [
            Strategy::GeneticAlgorithm,
            Strategy::Brkga,
            Strategy::SimulatedAnnealing,
        ] {
            let (_, len) = solve(strat, rots.clone());
            assert!(
                len <= blf_len + 1e-3,
                "{strat:?} strip length {len} > BLF {blf_len} on {} L-pieces",
                geoms[0].quantity()
            );
        }
    }

    /// Enlarging the allowed rotation set must never *worsen* the result
    /// (issue #3 expectation 2). Holds because BLF searches a superset of
    /// rotations (monotonic) and the floor caps the stochastic strategies at BLF.
    #[test]
    fn larger_rotation_set_never_worsens_strip_length() {
        for strat in [
            Strategy::BottomLeftFill,
            Strategy::GeneticAlgorithm,
            Strategy::Brkga,
        ] {
            let (_, small) = solve(strat, vec![0.0]);
            let (_, big) = solve(strat, vec![0.0, 90.0, 180.0, 270.0]);
            assert!(
                big <= small + 1e-3,
                "{strat:?}: larger rotation set worsened strip length {big} > {small}"
            );
        }
    }

    /// When the BLF floor overrides a metaheuristic's placements, the result must
    /// still carry the search's provenance (strategy label, generations, fitness)
    /// — the metaheuristic ran, only its layout was floored. On the concave
    /// L-instance BLF strictly beats the stochastic strategies, so this always
    /// exercises the floored branch (the bug: floored results returned a bare BLF
    /// with `generations = None`, failing any `strategy == Brkga` inspection).
    #[test]
    fn floored_result_keeps_metaheuristic_provenance() {
        let (geoms, boundary) = l_instance(vec![0.0, 90.0, 180.0, 270.0]);
        for (strat, label) in [
            (Strategy::GeneticAlgorithm, "GeneticAlgorithm"),
            (Strategy::Brkga, "BRKGA"),
        ] {
            let config = Config::default()
                .with_strategy(strat)
                .with_spacing(2.0)
                .with_seed(42)
                .with_time_limit(800);
            let r = Nester2D::new(config).solve(&geoms, &boundary).unwrap();
            assert_eq!(
                r.strategy.as_deref(),
                Some(label),
                "{strat:?}: floored result lost its strategy label"
            );
            assert!(
                r.generations.is_some(),
                "{strat:?}: floored result lost generation diagnostics"
            );
        }
    }

    /// The callback-driven path must be as reproducible as the plain path: with
    /// a seed set, two `solve_with_progress` runs must yield an identical layout.
    /// Before the fix the progress GA runner fell back to system entropy, so a
    /// seeded solve was non-deterministic whenever a progress callback was given
    /// (FFI `solve_2d_with_callback`, WASM/demo). Generation-bound termination
    /// (max_generations reached before the time limit on this small instance)
    /// makes the seed fully determine the result.
    #[test]
    fn progress_ga_is_reproducible_with_seed() {
        let (geometries, boundary) = instance();
        let config = Config::default()
            .with_strategy(Strategy::GeneticAlgorithm)
            .with_time_limit(1500)
            .with_seed(42);

        let a = Nester2D::new(config.clone())
            .solve_with_progress(&geometries, &boundary, Box::new(|_| {}))
            .unwrap();
        let b = Nester2D::new(config)
            .solve_with_progress(&geometries, &boundary, Box::new(|_| {}))
            .unwrap();

        assert_eq!(a.placements.len(), b.placements.len());
        for (pa, pb) in a.placements.iter().zip(b.placements.iter()) {
            assert_eq!(pa.geometry_id, pb.geometry_id);
            assert_eq!(pa.position, pb.position);
            assert_eq!(pa.rotation, pb.rotation);
        }
    }
}

/// Bucket B: containment (boundary escape), input validation, accounting, and
/// the used-footprint metric.
mod bucket_b_tests {
    use super::*;
    use u_nesting_d2::{is_placement_within_bounds, Placement};

    fn triangle_boundary() -> Boundary2D {
        // Right triangle: interior is x >= 0, y >= 0, x + y <= 1000.
        Boundary2D::new(vec![(0.0, 0.0), (1000.0, 0.0), (0.0, 1000.0)])
    }

    #[test]
    fn piece_outside_triangle_hypotenuse_is_rejected() {
        // A 150×150 square whose lower-left sits at (500, 500): its far corner
        // reaches (650, 650), where x + y = 1300 > 1000 — well outside the
        // hypotenuse. Its AABB is inside the boundary AABB, so only real
        // polygon-in-polygon containment can reject it (the escape the reporter hit).
        let boundary = triangle_boundary();
        let sq = Geometry2D::new("s").with_polygon(vec![
            (0.0, 0.0),
            (150.0, 0.0),
            (150.0, 150.0),
            (0.0, 150.0),
        ]);
        let outside = Placement::new_2d("s".to_string(), 0, 500.0, 500.0, 0.0);
        assert!(
            !is_placement_within_bounds(&outside, &sq, &boundary, 1e-6),
            "piece past the hypotenuse must be rejected"
        );

        // A square snug in the corner (far corner at (160,160), x+y=320 < 1000).
        let inside = Placement::new_2d("s".to_string(), 0, 10.0, 10.0, 0.0);
        assert!(
            is_placement_within_bounds(&inside, &sq, &boundary, 1e-6),
            "piece fully inside the triangle must be accepted"
        );
    }

    #[test]
    fn full_solve_on_triangle_never_returns_an_escaped_piece() {
        // End-to-end reproduction of the reporter's escape bug: solve() into a
        // non-rectangular (triangular) boundary must NOT return any placement that
        // sticks out past the hypotenuse, and the pieces that could not fit must be
        // accounted as unplaced (not silently dropped). This exercises the composed
        // pipeline — BLF/strategy places → validate_and_filter invokes the polygon
        // containment path → escaped pieces removed → counted in the accounting —
        // which the predicate-level tests above do not cover.
        let boundary = triangle_boundary(); // legs 1000, area 500_000
                                            // 20 × (200×200) squares: 800_000 of raw area into 500_000 of triangle,
                                            // and the triangle's tapering top cannot host full squares — some MUST be
                                            // rejected, so the run genuinely tests the reject-and-account path.
        let geometry = Geometry2D::new("sq")
            .with_polygon(vec![(0.0, 0.0), (200.0, 0.0), (200.0, 200.0), (0.0, 200.0)])
            .with_quantity(20);
        let geometries = vec![geometry.clone()];

        let nester = Nester2D::default_config();
        let result = nester.solve(&geometries, &boundary).unwrap();

        // Every returned placement must be genuinely inside the triangle — the
        // escape the reporter saw would surface here as a containment failure.
        for placement in &result.placements {
            assert!(
                is_placement_within_bounds(placement, &geometry, &boundary, 1e-6),
                "solve returned a placement outside the triangular boundary: {placement:?}"
            );
        }

        // The over-committed instance must leave real unplaced pieces, and the
        // accounting must reflect them (total_requested − placed > 0).
        let unplaced = result
            .total_requested
            .saturating_sub(result.placements.len());
        assert_eq!(result.total_requested, 20, "all 20 instances requested");
        assert!(
            unplaced > 0,
            "an over-committed triangle must leave pieces unplaced, got {} placed / {} requested",
            result.placements.len(),
            result.total_requested
        );
    }

    #[test]
    fn rectangular_boundary_still_uses_exact_aabb_path() {
        // Regression guard: the fast/exact AABB path for plain rectangles must
        // keep accepting flush placements (the polygon path would over-reject).
        let boundary = Boundary2D::rectangle(100.0, 100.0);
        let sq = Geometry2D::new("s").with_polygon(vec![
            (0.0, 0.0),
            (100.0, 0.0),
            (100.0, 100.0),
            (0.0, 100.0),
        ]);
        let flush = Placement::new_2d("s".to_string(), 0, 0.0, 0.0, 0.0);
        assert!(is_placement_within_bounds(&flush, &sq, &boundary, 1e-6));
    }

    #[test]
    fn bowtie_polygon_is_rejected() {
        let boundary = Boundary2D::rectangle(1000.0, 1000.0);
        // Self-intersecting bow-tie.
        let bowtie = Geometry2D::new("b").with_polygon(vec![
            (0.0, 0.0),
            (100.0, 100.0),
            (100.0, 0.0),
            (0.0, 100.0),
        ]);
        let nester = Nester2D::new(Config::default().with_strategy(Strategy::BottomLeftFill));
        assert!(
            nester.solve(&[bowtie], &boundary).is_err(),
            "self-intersecting polygon must be rejected"
        );
    }

    #[test]
    fn collinear_zero_area_polygon_is_rejected() {
        let boundary = Boundary2D::rectangle(1000.0, 1000.0);
        let collinear =
            Geometry2D::new("c").with_polygon(vec![(0.0, 0.0), (100.0, 0.0), (200.0, 0.0)]);
        let nester = Nester2D::new(Config::default().with_strategy(Strategy::BottomLeftFill));
        assert!(
            nester.solve(&[collinear], &boundary).is_err(),
            "degenerate (zero-area) polygon must be rejected"
        );
    }

    #[test]
    fn allow_flip_is_rejected_until_implemented() {
        let boundary = Boundary2D::rectangle(1000.0, 1000.0);
        let piece = Geometry2D::rectangle("r", 100.0, 50.0).with_flip(true);
        let nester = Nester2D::new(Config::default().with_strategy(Strategy::BottomLeftFill));
        assert!(
            nester.solve(&[piece], &boundary).is_err(),
            "allow_flip must error while mirroring is unimplemented"
        );
    }

    #[test]
    fn small_valid_piece_survives_degeneracy_check() {
        // A legitimately small piece (0.5×0.5, area 0.25) must NOT be rejected
        // by the zero-area guard.
        let boundary = Boundary2D::rectangle(100.0, 100.0);
        let tiny =
            Geometry2D::new("t").with_polygon(vec![(0.0, 0.0), (0.5, 0.0), (0.5, 0.5), (0.0, 0.5)]);
        let nester = Nester2D::new(Config::default().with_strategy(Strategy::BottomLeftFill));
        assert!(nester.solve(&[tiny], &boundary).is_ok());
    }

    #[test]
    fn used_bounding_box_is_padding_independent() {
        // Identical pieces on a fixed-width, very tall roll: the used footprint
        // (and used_utilization) must not collapse as boundary height grows,
        // unlike `utilization`.
        let geometries = vec![Geometry2D::rectangle("p", 100.0, 100.0).with_quantity(4)];
        let boundary = Boundary2D::rectangle(400.0, 100_000.0);
        let nester = Nester2D::new(Config::default().with_strategy(Strategy::BottomLeftFill));
        let result = nester.solve(&geometries, &boundary).unwrap();

        let [uw, uh] = result.used_bounding_box;
        assert!(uw > 0.0 && uh > 0.0, "used bbox populated");
        // Used footprint height must be far below the 100k boundary height.
        assert!(
            uh < 10_000.0,
            "used length reflects pieces, not boundary padding"
        );
        // Whole-boundary utilization is tiny; used-bbox area is a tight envelope.
        assert!(result.utilization < 0.01, "boundary utilization is diluted");
        assert!(uw * uh < 400.0 * 10_000.0, "used bbox is a tight envelope");
    }

    #[test]
    fn accounting_invariant_holds_on_overflow() {
        // Five 300×300 pieces into a 300×300 sheet: only one fits.
        let geometries = vec![Geometry2D::rectangle("p", 300.0, 300.0).with_quantity(5)];
        let boundary = Boundary2D::rectangle(300.0, 300.0);
        let nester = Nester2D::new(Config::default().with_strategy(Strategy::BottomLeftFill));
        let result = nester.solve(&geometries, &boundary).unwrap();

        assert_eq!(result.total_requested, 5);
        let unplaced_count = result.total_requested - result.placements.len();
        assert!(unplaced_count > 0, "some pieces must be unplaced");
        assert_eq!(
            result.placements.len() + unplaced_count,
            result.total_requested,
            "placed + unplaced_count == total_requested"
        );
    }
}

mod transform_integration_tests {
    use super::*;
    use std::f64::consts::PI;

    #[test]
    fn test_transform_geometry_vertices() {
        let geom = Geometry2D::rectangle("rect", 10.0, 5.0);
        let vertices = geom.outer_ring();

        // Apply a translation
        let t = Transform2D::translation(100.0, 50.0);
        let transformed: Vec<(f64, f64)> = vertices
            .iter()
            .map(|(x, y)| t.transform_point(*x, *y))
            .collect();

        // Check transformed vertices
        assert!((transformed[0].0 - 100.0).abs() < 1e-10);
        assert!((transformed[0].1 - 50.0).abs() < 1e-10);
        assert!((transformed[1].0 - 110.0).abs() < 1e-10);
        assert!((transformed[1].1 - 50.0).abs() < 1e-10);
    }

    #[test]
    fn test_rotated_geometry_aabb() {
        let geom = Geometry2D::rectangle("rect", 10.0, 2.0);
        let vertices = geom.outer_ring();

        // Rotate 90 degrees
        let t = Transform2D::rotation(PI / 2.0);
        let transformed: Vec<(f64, f64)> = vertices
            .iter()
            .map(|(x, y)| t.transform_point(*x, *y))
            .collect();

        // Compute AABB of transformed vertices
        let aabb = AABB2D::from_points(&transformed).unwrap();

        // After 90° rotation, a 10x2 rect becomes approximately 2x10
        // (with some floating point variance due to rotation around origin)
        let width = aabb.width();
        let height = aabb.height();
        assert!(
            (width - 2.0).abs() < 0.001 || (height - 2.0).abs() < 0.001,
            "width={}, height={}",
            width,
            height
        );
    }
}

mod stress_tests {
    use super::*;

    #[test]
    fn test_many_small_pieces() {
        let geometries = vec![Geometry2D::rectangle("tiny", 5.0, 5.0).with_quantity(100)];
        let boundary = Boundary2D::rectangle(500.0, 500.0);

        let nester = Nester2D::default_config();
        let result = nester.solve(&geometries, &boundary).unwrap();

        // Should place a reasonable number of pieces
        assert!(result.placements.len() >= 50);
        assert!(result.utilization > 0.0);
    }

    #[test]
    fn test_large_boundary() {
        let geometries = vec![Geometry2D::rectangle("medium", 50.0, 30.0).with_quantity(20)];
        let boundary = Boundary2D::rectangle(10000.0, 10000.0);

        let nester = Nester2D::default_config();
        let result = nester.solve(&geometries, &boundary).unwrap();

        // All pieces should fit in such a large boundary
        assert_eq!(result.placements.len(), 20);
        assert!(result.unplaced.is_empty());
    }
}