u-nesting-d2 0.26.0

//! Adaptive Large Neighborhood Search (ALNS) based 2D nesting optimization.
//!
//! This module provides ALNS-based optimization for 2D nesting problems,
//! implementing the algorithm from Ropke & Pisinger (2006).
//!
//! # Destroy Operators
//!
//! - **Random**: Remove random items from the solution
//! - **Worst**: Remove items with worst placement scores
//! - **Shaw**: Remove items related to a seed item (spatially nearby)
//!
//! # Repair Operators
//!
//! - **Greedy**: Largest item first, each at its bottom-left position
//! - **Random**: The removed items in random order, each at its bottom-left
//!   position

use crate::boundary::Boundary2D;
use crate::clamp_placement_to_boundary;
use crate::geometry::Geometry2D;
use crate::nfp::{
    compute_ifp_with_margin_and_mirror, find_bottom_left_placement, verify_no_overlap_mirrored,
    Nfp, PackingAxis, PlacedGeometry,
};
use std::sync::atomic::{AtomicBool, Ordering};
use std::sync::Arc;
use u_nesting_core::alns::{
    AlnsConfig, AlnsProblem, AlnsResult, AlnsRunner, AlnsSolution, DestroyOperatorId,
    DestroyResult, RepairOperatorId, RepairResult,
};
use u_nesting_core::geometry::{Boundary, Geometry};
use u_nesting_core::solver::{Config, ProgressCallback, ProgressInfo};
use u_nesting_core::timing::Timer;
use u_nesting_core::{Placement, SolveResult};

use crate::placement_utils::{hole_nfps, inset_boundary, InstanceInfo};
use rand::prelude::*;

/// A placed item in the ALNS solution.
#[derive(Debug, Clone)]
pub struct PlacedItem {
    /// Instance index.
    pub instance_idx: usize,
    /// X position.
    pub x: f64,
    /// Y position.
    pub y: f64,
    /// Rotation angle in radians.
    pub rotation: f64,
    /// Whether the item was placed mirrored (`allow_flip` support).
    pub mirrored: bool,
    /// Placement score (lower = better).
    pub score: f64,
}

/// ALNS solution for 2D nesting.
#[derive(Debug, Clone)]
pub struct AlnsNestingSolution {
    /// Placed items.
    pub placed: Vec<PlacedItem>,
    /// Unplaced instance indices.
    pub unplaced: Vec<usize>,
    /// Total number of instances.
    pub total_instances: usize,
    /// Total placed area.
    pub placed_area: f64,
    /// Boundary area.
    pub boundary_area: f64,
    /// How far the placed pieces reach along the boundary's length axis, from
    /// the boundary's start edge.
    pub used_length: f64,
    /// The boundary's extent across its length axis.
    pub cross_extent: f64,
}

impl AlnsNestingSolution {
    /// Create a new empty solution.
    pub fn new(total_instances: usize, boundary_area: f64) -> Self {
        Self {
            placed: Vec::new(),
            unplaced: (0..total_instances).collect(),
            total_instances,
            placed_area: 0.0,
            boundary_area,
            used_length: 0.0,
            cross_extent: 0.0,
        }
    }
}

impl AlnsSolution for AlnsNestingSolution {
    fn fitness(&self) -> f64 {
        // Fitness combines:
        // 1. Penalty for unplaced items (high weight)
        // 2. How loosely the placed pieces fill the strip they use: with the
        //    same pieces placed, the shorter layout scores lower. (The area
        //    over the whole boundary is the same for every such layout.)
        let unplaced_penalty = self.unplaced.len() as f64 * 1000.0;
        let used = self.used_length * self.cross_extent;
        let density = if self.placed_area > 0.0 && used > 0.0 {
            (self.placed_area / used).min(1.0)
        } else {
            0.0
        };
        unplaced_penalty + (1.0 - density)
    }

    fn placed_count(&self) -> usize {
        self.placed.len()
    }

    fn total_count(&self) -> usize {
        self.total_instances
    }
}

/// ALNS problem definition for 2D nesting.
pub struct AlnsNestingProblem {
    /// Input geometries.
    geometries: Vec<Geometry2D>,
    /// Boundary container.
    boundary: Boundary2D,
    /// Solver configuration.
    config: Config,
    /// Instance mapping.
    instances: Vec<InstanceInfo>,
    /// Available rotation angles per geometry.
    rotation_angles: Vec<Vec<f64>>,
    /// Geometry areas.
    geometry_areas: Vec<f64>,
    /// Cancellation flag.
    /// No-fit polygons between the pieces, kept across the layouts the search
    /// builds: they depend on the two shapes and their relative rotation, not on
    /// where the pieces lie.
    nfp_cache: crate::nfp::NfpCache,
    cancelled: Arc<AtomicBool>,
    /// Start time for timeout checking.
    start_time: Timer,
    /// Time limit in milliseconds.
    time_limit_ms: u64,
}

impl AlnsNestingProblem {
    /// Sets how far the placed pieces of `solution` reach along the boundary's
    /// length axis, from the boundary's start edge.
    fn refresh_extent(&self, solution: &mut AlnsNestingSolution) {
        let (axis, start, _) = crate::placement_utils::strip_frame(&self.boundary);
        let k = match axis {
            crate::nfp::PackingAxis::X => 0,
            crate::nfp::PackingAxis::Y => 1,
        };
        solution.used_length = solution
            .placed
            .iter()
            .map(|item| {
                let geom = &self.geometries[self.instances[item.instance_idx].geometry_idx];
                let (_, hi) = geom.aabb_at_rotation_mirrored(item.rotation, item.mirrored);
                [item.x, item.y][k] + hi[k]
            })
            .fold(start, f64::max)
            - start;
    }

    /// Creates a new ALNS nesting problem.
    pub fn new(
        geometries: Vec<Geometry2D>,
        boundary: Boundary2D,
        config: Config,
        cancelled: Arc<AtomicBool>,
        time_limit_ms: u64,
    ) -> Self {
        let mut instances = Vec::new();
        let mut rotation_angles = Vec::new();
        let mut geometry_areas = Vec::new();

        for (geom_idx, geom) in geometries.iter().enumerate() {
            let angles = geom.rotations();
            let angles = if angles.is_empty() { vec![0.0] } else { angles };
            rotation_angles.push(angles);

            let area = geom.measure();
            geometry_areas.push(area);

            for instance_num in 0..geom.quantity() {
                instances.push(InstanceInfo {
                    geometry_idx: geom_idx,
                    instance_num,
                });
            }
        }

        Self {
            geometries,
            boundary,
            config,
            instances,
            rotation_angles,
            geometry_areas,
            nfp_cache: crate::nfp::NfpCache::with_capacity(20_000),
            cancelled,
            start_time: Timer::now(),
            time_limit_ms,
        }
    }

    /// Check if timeout has been reached.
    fn is_timed_out(&self) -> bool {
        if self.time_limit_ms == 0 {
            return false;
        }
        self.start_time.elapsed_ms() >= self.time_limit_ms
    }

    /// Returns the total number of instances.
    pub fn num_instances(&self) -> usize {
        self.instances.len()
    }

    /// Compute sample step for grid search.
    fn compute_sample_step(&self) -> f64 {
        let (min, max) = self.boundary.aabb();
        let width = max[0] - min[0];
        (width / 100.0).max(1.0)
    }

    /// Try to place an item at the best position using NFP.
    fn try_place_item(
        &self,
        instance_idx: usize,
        placed_geometries: &[PlacedGeometry],
        boundary_polygon: &[(f64, f64)],
        sample_step: f64,
    ) -> Option<PlacedItem> {
        let info = &self.instances[instance_idx];
        let geom = &self.geometries[info.geometry_idx];
        let angles = &self.rotation_angles[info.geometry_idx];
        // Mirror candidates (`allow_flip` support) — same pattern as
        // `nester.rs`'s `mirror_candidates` helper.
        let mirror_candidates: &[bool] = if geom.allow_flip() {
            &[false, true]
        } else {
            &[false]
        };

        let mut best_placement: Option<PlacedItem> = None;
        let axis = PackingAxis::of(&self.boundary);

        for &rotation in angles {
            for &mirror in mirror_candidates {
                let ifp = match compute_ifp_with_margin_and_mirror(
                    boundary_polygon,
                    geom,
                    rotation,
                    0.0,
                    mirror,
                ) {
                    Ok(ifp) => ifp,
                    Err(_) => continue,
                };

                if ifp.is_empty() {
                    continue;
                }

                let spacing = self.config.spacing;
                let mut nfps: Vec<Nfp> = crate::placement_utils::nfps_against_placed(
                    &self.nfp_cache,
                    placed_geometries,
                    geom,
                    rotation,
                    mirror,
                    spacing,
                );

                // `spacing` separates pieces from each other, not from the boundary —
                // clearance to the edge is `margin`, already applied to the boundary.
                nfps.extend(hole_nfps(
                    &self.boundary,
                    geom,
                    rotation,
                    mirror,
                    self.config.margin,
                ));
                let nfp_refs: Vec<&Nfp> = nfps.iter().collect();

                // IFP returns positions where the geometry's origin should be placed.
                // Clamp to ensure placement keeps geometry within boundary.
                if let Some((x, y)) = find_bottom_left_placement(&ifp, &nfp_refs, sample_step, axis)
                {
                    // Clamp position to keep geometry within boundary
                    // (mirror-aware — an unmirrored AABB has the wrong local
                    // extents for a mirrored candidate, see `aabb_at_rotation_mirrored`).
                    let geom_aabb = geom.aabb_at_rotation_mirrored(rotation, mirror);
                    let boundary_aabb = self.boundary.aabb();

                    if let Some((clamped_x, clamped_y)) =
                        clamp_placement_to_boundary(x, y, geom_aabb, boundary_aabb)
                    {
                        // Only verify overlap if clamping changed the position
                        // The original NFP-found position is already collision-free by definition
                        let was_clamped =
                            (clamped_x - x).abs() > 1e-6 || (clamped_y - y).abs() > 1e-6;
                        if was_clamped {
                            // Verify no actual polygon overlap using SAT
                            if !verify_no_overlap_mirrored(
                                geom,
                                (clamped_x, clamped_y),
                                rotation,
                                mirror,
                                placed_geometries,
                            ) {
                                continue; // Skip - clamped position would cause overlap
                            }
                        }

                        let earlier = best_placement.as_ref().is_none_or(|best| {
                            axis.precedes((clamped_x, clamped_y), (best.x, best.y), 0.0)
                        });
                        if earlier {
                            best_placement = Some(PlacedItem {
                                instance_idx,
                                x: clamped_x,
                                y: clamped_y,
                                rotation,
                                mirrored: mirror,
                                score: axis.key((clamped_x, clamped_y)).0,
                            });
                        }
                    }
                }
            }
        }

        best_placement
    }

    /// Place items using BLF heuristic.
    fn place_items_blf(&self, items: &[usize], solution: &mut AlnsNestingSolution) {
        let margin = self.config.margin;
        let boundary_polygon = inset_boundary(&self.boundary, margin);
        let sample_step = self.compute_sample_step();

        let mut placed_geometries: Vec<PlacedGeometry> = Vec::new();
        for item in &solution.placed {
            let info = &self.instances[item.instance_idx];
            let geom = &self.geometries[info.geometry_idx];
            placed_geometries.push(PlacedGeometry {
                geometry: geom.clone(),
                position: (item.x, item.y),
                rotation: item.rotation,
                mirrored: item.mirrored,
            });
        }

        // Sort items by area (largest first)
        let mut sorted_items = items.to_vec();
        sorted_items.sort_by(|&a, &b| {
            let area_a = self.geometry_areas[self.instances[a].geometry_idx];
            let area_b = self.geometry_areas[self.instances[b].geometry_idx];
            area_b
                .partial_cmp(&area_a)
                .unwrap_or(std::cmp::Ordering::Equal)
        });

        for &instance_idx in &sorted_items {
            // Check cancellation and timeout
            if self.cancelled.load(Ordering::Relaxed) || self.is_timed_out() {
                break;
            }

            if let Some(placement) = self.try_place_item(
                instance_idx,
                &placed_geometries,
                &boundary_polygon,
                sample_step,
            ) {
                let info = &self.instances[instance_idx];
                let area = self.geometry_areas[info.geometry_idx];

                solution.placed_area += area;

                let geom = &self.geometries[info.geometry_idx];
                placed_geometries.push(PlacedGeometry {
                    geometry: geom.clone(),
                    position: (placement.x, placement.y),
                    rotation: placement.rotation,
                    mirrored: placement.mirrored,
                });

                solution.placed.push(placement);
                self.refresh_extent(solution);
                solution.unplaced.retain(|&idx| idx != instance_idx);
            }
        }
    }

    /// Remove item from solution.
    fn remove_item(&self, solution: &mut AlnsNestingSolution, instance_idx: usize) {
        if let Some(pos) = solution
            .placed
            .iter()
            .position(|p| p.instance_idx == instance_idx)
        {
            let item = solution.placed.remove(pos);
            let info = &self.instances[item.instance_idx];
            solution.placed_area -= self.geometry_areas[info.geometry_idx];
            solution.unplaced.push(item.instance_idx);
        }

        self.refresh_extent(solution);
    }
}

impl AlnsProblem for AlnsNestingProblem {
    type Solution = AlnsNestingSolution;

    fn create_initial_solution(&mut self) -> AlnsNestingSolution {
        let boundary_area = self.boundary.measure();
        let mut solution = AlnsNestingSolution::new(self.instances.len(), boundary_area);
        solution.cross_extent = crate::placement_utils::strip_frame(&self.boundary).2;

        let all_items: Vec<usize> = (0..self.instances.len()).collect();
        self.place_items_blf(&all_items, &mut solution);

        solution
    }

    fn clone_solution(&self, solution: &AlnsNestingSolution) -> AlnsNestingSolution {
        solution.clone()
    }

    fn destroy_operators(&self) -> Vec<DestroyOperatorId> {
        vec![
            DestroyOperatorId::Random,
            DestroyOperatorId::Worst,
            DestroyOperatorId::Shaw,
        ]
    }

    fn repair_operators(&self) -> Vec<RepairOperatorId> {
        vec![RepairOperatorId::Greedy, RepairOperatorId::Random]
    }

    fn destroy(
        &mut self,
        solution: &mut AlnsNestingSolution,
        operator: DestroyOperatorId,
        degree: f64,
        rng: &mut rand::rngs::StdRng,
    ) -> DestroyResult {
        let num_to_remove = ((solution.placed.len() as f64 * degree).ceil() as usize).max(1);
        let mut removed_indices = Vec::new();

        if solution.placed.is_empty() {
            return DestroyResult {
                removed_indices,
                operator,
            };
        }

        match operator {
            DestroyOperatorId::Random => {
                // Random removal
                let mut indices: Vec<usize> =
                    solution.placed.iter().map(|p| p.instance_idx).collect();
                indices.shuffle(rng);

                for &idx in indices.iter().take(num_to_remove) {
                    removed_indices.push(idx);
                }
            }
            DestroyOperatorId::Worst => {
                // Worst removal (highest Y position = worst)
                let mut items_with_score: Vec<(usize, f64)> = solution
                    .placed
                    .iter()
                    .map(|p| (p.instance_idx, p.score))
                    .collect();

                items_with_score
                    .sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal));

                for (idx, _) in items_with_score.iter().take(num_to_remove) {
                    removed_indices.push(*idx);
                }
            }
            DestroyOperatorId::Shaw => {
                // Cluster removal (same logic for both)
                let seed_idx = rng.random_range(0..solution.placed.len());
                let seed = &solution.placed[seed_idx];
                let seed_x = seed.x;
                let seed_y = seed.y;

                let mut items_with_distance: Vec<(usize, f64)> = solution
                    .placed
                    .iter()
                    .map(|item| {
                        let dx = item.x - seed_x;
                        let dy = item.y - seed_y;
                        (item.instance_idx, (dx * dx + dy * dy).sqrt())
                    })
                    .collect();

                items_with_distance
                    .sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal));

                for (idx, _) in items_with_distance.iter().take(num_to_remove) {
                    removed_indices.push(*idx);
                }
            }
            DestroyOperatorId::Custom(_) => {
                // Fall back to random for custom operators
                let mut indices: Vec<usize> =
                    solution.placed.iter().map(|p| p.instance_idx).collect();
                indices.shuffle(rng);

                for &idx in indices.iter().take(num_to_remove) {
                    removed_indices.push(idx);
                }
            }
        }

        // Remove items from solution
        for &idx in &removed_indices {
            self.remove_item(solution, idx);
        }

        DestroyResult {
            removed_indices,
            operator,
        }
    }

    fn repair(
        &mut self,
        solution: &mut AlnsNestingSolution,
        _destroyed: &DestroyResult,
        operator: RepairOperatorId,
        rng: &mut rand::rngs::StdRng,
    ) -> RepairResult {
        let items_to_place = solution.unplaced.clone();
        let initial_placed = solution.placed.len();

        match operator {
            RepairOperatorId::Greedy => {
                // Largest first, each at its bottom-left position.
                self.place_items_blf(&items_to_place, solution);
            }
            RepairOperatorId::Random => {
                // Random order placement
                let mut shuffled = items_to_place.clone();
                shuffled.shuffle(rng);
                self.place_items_blf(&shuffled, solution);
            }
            RepairOperatorId::Custom(_) => {
                self.place_items_blf(&items_to_place, solution);
            }
        }

        RepairResult {
            placed_count: solution.placed.len() - initial_placed,
            unplaced_count: solution.unplaced.len(),
            operator,
        }
    }

    fn relatedness(&self, solution: &AlnsNestingSolution, i: usize, j: usize) -> f64 {
        // Relatedness based on spatial distance
        let item_i = solution.placed.iter().find(|p| p.instance_idx == i);
        let item_j = solution.placed.iter().find(|p| p.instance_idx == j);

        match (item_i, item_j) {
            (Some(a), Some(b)) => {
                let dx = a.x - b.x;
                let dy = a.y - b.y;
                1.0 / (1.0 + (dx * dx + dy * dy).sqrt())
            }
            _ => 0.0,
        }
    }
}

/// Run ALNS nesting optimization.
///
/// # Errors
/// `ConfigError` when the algorithm configuration is out of range.
pub fn run_alns_nesting(
    geometries: &[Geometry2D],
    boundary: &Boundary2D,
    config: &Config,
    alns_config: &AlnsConfig,
    cancelled: Arc<AtomicBool>,
    progress: Option<&ProgressCallback>,
) -> u_nesting_core::Result<SolveResult<f64>> {
    let mut problem = AlnsNestingProblem::new(
        geometries.to_vec(),
        boundary.clone(),
        config.clone(),
        cancelled.clone(),
        alns_config.time_limit_ms,
    );

    let runner = AlnsRunner::with_cancellation(alns_config.clone(), cancelled)?;
    let report = |iteration: usize, best_fitness: f64, elapsed_ms: u64, running: bool| {
        if let Some(callback) = progress {
            callback(ProgressInfo::search_step(
                "ALNS",
                iteration as u64,
                alns_config.max_iterations as u64,
                best_fitness,
                elapsed_ms,
                running,
            ));
        }
    };
    let alns_result: AlnsResult<AlnsNestingSolution> = runner.run(&mut problem, |p| {
        report(p.iteration, p.best_fitness, p.elapsed_ms, true);
    });
    report(
        alns_result.iterations,
        alns_result.best_fitness,
        alns_result.elapsed_ms,
        false,
    );

    let mut result = SolveResult::new();

    for item in &alns_result.best_solution.placed {
        let info = &problem.instances[item.instance_idx];
        let geom = &problem.geometries[info.geometry_idx];

        result.placements.push(
            Placement::new_2d(
                geom.id().to_string(),
                info.instance_num,
                item.x,
                item.y,
                item.rotation,
            )
            .with_mirrored(item.mirrored),
        );
    }

    result.boundaries_used = if result.placements.is_empty() { 0 } else { 1 };
    result.utilization =
        alns_result.best_solution.placed_area / alns_result.best_solution.boundary_area;
    result.computation_time_ms = alns_result.elapsed_ms;
    result.iterations = Some(alns_result.iterations as u64);
    result.stop_reason = alns_result.stop_reason;
    result.best_fitness = Some(alns_result.best_fitness);
    result.strategy = Some("ALNS".to_string());

    Ok(result)
}

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

    fn create_test_geometries() -> Vec<Geometry2D> {
        vec![
            Geometry2D::rectangle("rect1", 50.0, 30.0).with_quantity(3),
            Geometry2D::rectangle("rect2", 40.0, 40.0).with_quantity(2),
            Geometry2D::rectangle("rect3", 60.0, 20.0).with_quantity(2),
        ]
    }

    fn create_test_boundary() -> Boundary2D {
        Boundary2D::rectangle(300.0, 200.0)
    }

    #[test]
    fn test_alns_nesting_problem_creation() {
        let geometries = create_test_geometries();
        let boundary = create_test_boundary();
        let config = Config::default();
        let cancelled = Arc::new(AtomicBool::new(false));

        let problem = AlnsNestingProblem::new(geometries, boundary, config, cancelled, 60000);

        assert_eq!(problem.num_instances(), 7);
    }

    #[test]
    fn test_alns_nesting_initial_solution() {
        let geometries = create_test_geometries();
        let boundary = create_test_boundary();
        let config = Config::default();
        let cancelled = Arc::new(AtomicBool::new(false));

        let mut problem = AlnsNestingProblem::new(geometries, boundary, config, cancelled, 60000);
        let solution = problem.create_initial_solution();

        assert!(!solution.placed.is_empty());
        assert!(solution.placed_area > 0.0);
    }

    #[test]
    fn a_shorter_layout_of_the_same_pieces_scores_lower() {
        let mut solution = AlnsNestingSolution::new(2, 60000.0);
        solution.unplaced.clear();
        solution.placed_area = 400.0;
        solution.cross_extent = 20.0;
        solution.used_length = 20.0;
        let short = solution.fitness();
        solution.used_length = 50.0;
        let long = solution.fitness();
        assert!(short < long, "{short} {long}");
        // A piece left out outweighs any layout length.
        solution.unplaced.push(0);
        solution.used_length = 20.0;
        assert!(solution.fitness() > long + 900.0);
    }

    #[test]
    fn test_alns_nesting_solution_fitness() {
        let solution = AlnsNestingSolution {
            placed: vec![
                PlacedItem {
                    instance_idx: 0,
                    x: 10.0,
                    y: 10.0,
                    rotation: 0.0,
                    mirrored: false,
                    score: 10.0,
                },
                PlacedItem {
                    instance_idx: 1,
                    x: 60.0,
                    y: 10.0,
                    rotation: 0.0,
                    mirrored: false,
                    score: 10.0,
                },
            ],
            unplaced: vec![2],
            total_instances: 3,
            placed_area: 3000.0,
            boundary_area: 60000.0,
            used_length: 50.0,
            cross_extent: 100.0,
        };

        let fitness = solution.fitness();
        assert!(fitness > 0.0);
        assert!(fitness >= 1000.0); // 1 unplaced item penalty
    }

    #[test]
    fn test_alns_nesting_destroy_random() {
        use rand::SeedableRng;

        let geometries = create_test_geometries();
        let boundary = create_test_boundary();
        let config = Config::default();
        let cancelled = Arc::new(AtomicBool::new(false));

        let mut problem = AlnsNestingProblem::new(geometries, boundary, config, cancelled, 60000);
        let mut solution = problem.create_initial_solution();

        let initial_placed = solution.placed.len();
        let mut rng = rand::rngs::StdRng::seed_from_u64(42);

        let result = problem.destroy(&mut solution, DestroyOperatorId::Random, 0.3, &mut rng);

        assert!(!result.removed_indices.is_empty());
        assert_eq!(result.operator, DestroyOperatorId::Random);
        assert!(solution.placed.len() < initial_placed);
    }

    #[test]
    fn test_alns_nesting_destroy_worst() {
        use rand::SeedableRng;

        let geometries = create_test_geometries();
        let boundary = create_test_boundary();
        let config = Config::default();
        let cancelled = Arc::new(AtomicBool::new(false));

        let mut problem = AlnsNestingProblem::new(geometries, boundary, config, cancelled, 60000);
        let mut solution = problem.create_initial_solution();

        let initial_placed = solution.placed.len();
        let mut rng = rand::rngs::StdRng::seed_from_u64(42);

        let result = problem.destroy(&mut solution, DestroyOperatorId::Worst, 0.3, &mut rng);

        assert!(!result.removed_indices.is_empty());
        assert_eq!(result.operator, DestroyOperatorId::Worst);
        assert!(solution.placed.len() < initial_placed);
    }

    #[test]
    fn test_alns_nesting_repair() {
        use rand::SeedableRng;

        let geometries = create_test_geometries();
        let boundary = create_test_boundary();
        let config = Config::default();
        let cancelled = Arc::new(AtomicBool::new(false));

        let mut problem = AlnsNestingProblem::new(geometries, boundary, config, cancelled, 60000);
        let mut solution = problem.create_initial_solution();

        let mut rng = rand::rngs::StdRng::seed_from_u64(42);

        let destroy_result =
            problem.destroy(&mut solution, DestroyOperatorId::Random, 0.5, &mut rng);
        let after_destroy_placed = solution.placed.len();

        let repair_result = problem.repair(
            &mut solution,
            &destroy_result,
            RepairOperatorId::Greedy,
            &mut rng,
        );

        assert!(repair_result.placed_count > 0 || after_destroy_placed == solution.placed.len());
        assert_eq!(repair_result.operator, RepairOperatorId::Greedy);
    }

    #[test]
    fn test_run_alns_nesting() {
        let geometries = create_test_geometries();
        let boundary = create_test_boundary();
        let config = Config::default();
        let alns_config = AlnsConfig::new()
            .with_max_iterations(50)
            .with_time_limit_ms(5000);
        let cancelled = Arc::new(AtomicBool::new(false));

        let result = run_alns_nesting(
            &geometries,
            &boundary,
            &config,
            &alns_config,
            cancelled,
            None,
        )
        .expect("valid config");

        assert!(!result.placements.is_empty());
        assert!(result.utilization > 0.0);
    }

    #[test]
    fn test_alns_nesting_full_cycle() {
        let geometries = create_test_geometries();
        let boundary = create_test_boundary();
        let config = Config::default();
        let cancelled = Arc::new(AtomicBool::new(false));

        let mut problem = AlnsNestingProblem::new(geometries, boundary, config, cancelled, 60000);

        let alns_config = AlnsConfig::new().with_max_iterations(10).with_seed(42);

        let runner = AlnsRunner::new(alns_config).expect("valid config");
        let result: AlnsResult<AlnsNestingSolution> = runner.run(&mut problem, |progress| {
            assert!(progress.iteration <= 10);
        });

        assert!(result.iterations <= 10);
        assert!(!result.best_solution.placed.is_empty());
    }

    #[test]
    fn test_alns_destroy_operators() {
        let geometries = create_test_geometries();
        let boundary = create_test_boundary();
        let config = Config::default();
        let cancelled = Arc::new(AtomicBool::new(false));

        let problem = AlnsNestingProblem::new(geometries, boundary, config, cancelled, 60000);
        let operators = problem.destroy_operators();

        assert!(operators.contains(&DestroyOperatorId::Random));
        assert!(operators.contains(&DestroyOperatorId::Worst));
        assert!(operators.contains(&DestroyOperatorId::Shaw));
    }

    #[test]
    fn test_alns_repair_operators() {
        let geometries = create_test_geometries();
        let boundary = create_test_boundary();
        let config = Config::default();
        let cancelled = Arc::new(AtomicBool::new(false));

        let problem = AlnsNestingProblem::new(geometries, boundary, config, cancelled, 60000);
        let operators = problem.repair_operators();

        assert!(operators.contains(&RepairOperatorId::Greedy));
        assert!(operators.contains(&RepairOperatorId::Random));
    }

    /// Chiral L-shape — see `nfp.rs`'s `chiral_l` fixture for why this
    /// specific shape (asymmetric width/height/notch, no reflection symmetry).
    fn chiral_l(id: &str) -> Geometry2D {
        Geometry2D::l_shape(id, 30.0, 20.0, 20.0, 10.0)
    }

    fn polygons_overlap(a: &[(f64, f64)], b: &[(f64, f64)]) -> bool {
        for i in 0..a.len() {
            let (a1, a2) = (a[i], a[(i + 1) % a.len()]);
            for j in 0..b.len() {
                let (b1, b2) = (b[j], b[(j + 1) % b.len()]);
                if crate::polygon_ops::segments_intersect(a1, a2, b1, b2) {
                    return true;
                }
            }
        }
        false
    }

    /// `allow_flip`/mirroring, ALNS strategy. `try_place_item` calls no
    /// `.validate()`, so calling it directly genuinely bypasses the public
    /// `allow_flip = true` rejection — same bypass strategy as GA/SA/
    /// BRKGA/GDRR.
    #[test]
    fn test_alns_try_place_item_mirror_no_overlap() {
        let geometries = vec![chiral_l("L").with_flip(true).with_quantity(2)];
        let boundary = Boundary2D::rectangle(65.0, 45.0);
        let config = Config::default().with_spacing(1.0);
        let problem = AlnsNestingProblem::new(
            geometries.clone(),
            boundary,
            config,
            Arc::new(AtomicBool::new(false)),
            60000,
        );

        let margin = problem.config.margin;
        let boundary_polygon = inset_boundary(&problem.boundary, margin);
        let sample_step = problem.compute_sample_step();

        let placement0 = problem
            .try_place_item(0, &[], &boundary_polygon, sample_step)
            .expect("first piece must fit");

        let placed_geometries = vec![PlacedGeometry {
            geometry: geometries[0].clone(),
            position: (placement0.x, placement0.y),
            rotation: placement0.rotation,
            mirrored: placement0.mirrored,
        }];
        let placement1 = problem
            .try_place_item(1, &placed_geometries, &boundary_polygon, sample_step)
            .expect("second piece must fit avoiding the first");

        let poly0 = PlacedGeometry {
            geometry: geometries[0].clone(),
            position: (placement0.x, placement0.y),
            rotation: placement0.rotation,
            mirrored: placement0.mirrored,
        }
        .translated_exterior();
        let poly1 = PlacedGeometry {
            geometry: geometries[0].clone(),
            position: (placement1.x, placement1.y),
            rotation: placement1.rotation,
            mirrored: placement1.mirrored,
        }
        .translated_exterior();
        assert!(
            !polygons_overlap(&poly0, &poly1),
            "instance 0 (mirrored={}) and instance 1 (mirrored={}) must not overlap",
            placement0.mirrored,
            placement1.mirrored
        );
    }

    #[test]
    fn test_alns_try_place_item_mirror_ignored_without_allow_flip() {
        let geometries = vec![chiral_l("L").with_quantity(1)];
        let boundary = Boundary2D::rectangle(65.0, 45.0);
        let problem = AlnsNestingProblem::new(
            geometries,
            boundary,
            Config::default(),
            Arc::new(AtomicBool::new(false)),
            60000,
        );

        let margin = problem.config.margin;
        let boundary_polygon = inset_boundary(&problem.boundary, margin);
        let sample_step = problem.compute_sample_step();

        let placement = problem
            .try_place_item(0, &[], &boundary_polygon, sample_step)
            .expect("piece must fit");
        assert!(
            !placement.mirrored,
            "allow_flip=false must suppress mirroring"
        );
    }
}