pdp_lns 0.1.1

use crate::instance::Instance;
use crate::solution::RouteInfo;

/// Maximum segment length for inter-route exchange.
const MAX_SEG: usize = 3;

/// Inter-route segment exchange: exchange contiguous segments between two routes.
///
/// For each pair of routes (r1, r2), try replacing a segment of k1 consecutive
/// customers from r1 with a segment of k2 consecutive customers from r2 (and
/// vice versa), where k1, k2 in 1..=MAX_SEG.
///
/// This generalizes pair-level M2/M3 to arbitrary contiguous segments.
/// First improvement: returns true if any improvement was found and applied.
pub fn apply_segment_exchange(
    inst: &Instance,
    routes: &mut [Vec<usize>],
    infos: &mut [RouteInfo],
) -> bool {
    let nr = routes.len();
    if nr < 2 {
        return false;
    }

    let mut new_r1: Vec<usize> = Vec::new();
    let mut new_r2: Vec<usize> = Vec::new();
    let mut info_buf1 = RouteInfo::new();
    let mut info_buf2 = RouteInfo::new();
    // Precomputed position arrays for O(1) partner lookup in segment_pairs_intact
    let mut pos1 = vec![usize::MAX; inst.n + 1];
    let mut pos2 = vec![usize::MAX; inst.n + 1];

    for ri in 0..nr {
        // Set pos1 for route ri (sparse write, cleared after rj loop)
        for (idx, &v) in routes[ri].iter().enumerate() {
            if v != 0 && v <= inst.n {
                pos1[v] = idx;
            }
        }
        for rj in (ri + 1)..nr {
            let len1 = routes[ri].len(); // includes depot bookends
            let len2 = routes[rj].len();
            if len1 <= 2 && len2 <= 2 {
                continue;
            }
            // Set pos2 for route rj (sparse write, cleared at end of rj iteration)
            for (idx, &v) in routes[rj].iter().enumerate() {
                if v != 0 && v <= inst.n {
                    pos2[v] = idx;
                }
            }

            let base_dist = infos[ri].distance + infos[rj].distance;

            // Restructured loops: (s1_start, s2_start) outer, (s1_len, s2_len) inner.
            // Arc checks that depend only on (s1_start, s2_start) — specifically
            // (r1_before, seg2_first) and (r2_before, seg1_first) — are hoisted
            // before the inner loops, skipping all 9 (s1_len, s2_len) combinations
            // when these position-only checks fail (~86% of position pairs).
            for s1_start in 1..len1.saturating_sub(1) {
                let r1_before = routes[ri][s1_start - 1];
                let seg1_first = routes[ri][s1_start];

                // Precompute seg1 data for each segment length (1..=MAX_SEG)
                let max_s1 = MAX_SEG.min(len1 - 1 - s1_start);
                let mut seg1_demands = [0i32; MAX_SEG];
                let mut seg1_lasts = [0usize; MAX_SEG];
                let mut r1_afters = [0usize; MAX_SEG];
                let mut r1_removeds = [0.0f64; MAX_SEG];
                let r1_removed_base = inst.dist(r1_before, seg1_first);
                {
                    let mut demand_acc = 0i32;
                    for k in 0..max_s1 {
                        demand_acc += inst.demand[routes[ri][s1_start + k]];
                        seg1_demands[k] = demand_acc;
                        seg1_lasts[k] = routes[ri][s1_start + k];
                        r1_afters[k] = routes[ri][s1_start + k + 1];
                        r1_removeds[k] = r1_removed_base + inst.dist(seg1_lasts[k], r1_afters[k]);
                    }
                }

                for s2_start in 1..len2.saturating_sub(1) {
                    let r2_before = routes[rj][s2_start - 1];
                    let seg2_first = routes[rj][s2_start];

                    // Hoisted arc checks: depend only on (s1_start, s2_start)
                    if !inst.is_arc_feasible(r1_before, seg2_first)
                        || !inst.is_arc_feasible(r2_before, seg1_first)
                    {
                        continue;
                    }

                    // Precompute seg2 data for each segment length
                    let max_s2 = MAX_SEG.min(len2 - 1 - s2_start);
                    let mut seg2_demands = [0i32; MAX_SEG];
                    let mut seg2_lasts = [0usize; MAX_SEG];
                    let mut r2_afters = [0usize; MAX_SEG];
                    let mut r2_removeds = [0.0f64; MAX_SEG];
                    let r2_removed_base = inst.dist(r2_before, seg2_first);
                    {
                        let mut demand_acc = 0i32;
                        for k in 0..max_s2 {
                            demand_acc += inst.demand[routes[rj][s2_start + k]];
                            seg2_demands[k] = demand_acc;
                            seg2_lasts[k] = routes[rj][s2_start + k];
                            r2_afters[k] = routes[rj][s2_start + k + 1];
                            r2_removeds[k] =
                                r2_removed_base + inst.dist(seg2_lasts[k], r2_afters[k]);
                        }
                    }

                    // Precompute distance components constant for (s1_start, s2_start)
                    let c_r1_new_base = inst.dist(r1_before, seg2_first);
                    let c_r2_new_base = inst.dist(r2_before, seg1_first);

                    for k1 in 0..max_s1 {
                        let s1_end = s1_start + k1 + 1;

                        for k2 in 0..max_s2 {
                            let s2_end = s2_start + k2 + 1;

                            // Arc checks that depend on segment endpoints
                            if !inst.is_arc_feasible(seg2_lasts[k2], r1_afters[k1])
                                || !inst.is_arc_feasible(seg1_lasts[k1], r2_afters[k2])
                            {
                                continue;
                            }

                            // New edge costs (partially precomputed)
                            let r1_new_edges =
                                c_r1_new_base + inst.dist(seg2_lasts[k2], r1_afters[k1]);
                            let r2_new_edges =
                                c_r2_new_base + inst.dist(seg1_lasts[k1], r2_afters[k2]);

                            let delta =
                                (r1_new_edges - r1_removeds[k1]) + (r2_new_edges - r2_removeds[k2]);

                            // Distance pre-filter
                            if delta >= -1e-10 {
                                continue;
                            }

                            // Capacity pre-filter
                            let demand_shift_r1 = seg2_demands[k2] - seg1_demands[k1];
                            let demand_shift_r2 = seg1_demands[k1] - seg2_demands[k2];

                            if !capacity_feasible(
                                inst,
                                &routes[ri],
                                s1_start,
                                s1_end,
                                demand_shift_r1,
                            ) {
                                continue;
                            }
                            if !capacity_feasible(
                                inst,
                                &routes[rj],
                                s2_start,
                                s2_end,
                                demand_shift_r2,
                            ) {
                                continue;
                            }

                            // Precedence pre-filter (O(seg_len) with precomputed positions)
                            if !precedence_feasible_exchange(
                                inst,
                                &routes[ri],
                                s1_start,
                                s1_end,
                                &pos1,
                                &routes[rj],
                                s2_start,
                                s2_end,
                                &pos2,
                            ) {
                                continue;
                            }

                            // Build candidate routes and check full feasibility
                            build_exchanged_route(
                                &routes[ri],
                                s1_start,
                                s1_end,
                                &routes[rj],
                                s2_start,
                                s2_end,
                                &mut new_r1,
                            );
                            build_exchanged_route(
                                &routes[rj],
                                s2_start,
                                s2_end,
                                &routes[ri],
                                s1_start,
                                s1_end,
                                &mut new_r2,
                            );

                            info_buf1.compute(inst, &new_r1);
                            info_buf2.compute(inst, &new_r2);

                            let new_dist = info_buf1.distance + info_buf2.distance;
                            if new_dist >= base_dist - 1e-10 {
                                continue;
                            }

                            if !is_route_feasible_full(inst, &new_r1, &info_buf1)
                                || !is_route_feasible_full(inst, &new_r2, &info_buf2)
                            {
                                continue;
                            }

                            // Apply the exchange
                            routes[ri] = std::mem::take(&mut new_r1);
                            routes[rj] = std::mem::take(&mut new_r2);
                            infos[ri].compute(inst, &routes[ri]);
                            infos[rj].compute(inst, &routes[rj]);
                            return true;
                        }
                    }
                }
            }
            // Clear pos2 (sparse: only entries we set)
            for &v in routes[rj].iter() {
                if v != 0 && v <= inst.n {
                    pos2[v] = usize::MAX;
                }
            }
        }
        // Clear pos1 (sparse: only entries we set)
        for &v in routes[ri].iter() {
            if v != 0 && v <= inst.n {
                pos1[v] = usize::MAX;
            }
        }
    }

    false
}

/// Build a new route by replacing the segment [seg_start..seg_end) in `host`
/// with the segment [donor_start..donor_end) from `donor`.
fn build_exchanged_route(
    host: &[usize],
    seg_start: usize,
    seg_end: usize,
    donor: &[usize],
    donor_start: usize,
    donor_end: usize,
    buf: &mut Vec<usize>,
) {
    buf.clear();
    buf.extend_from_slice(&host[..seg_start]);
    buf.extend_from_slice(&donor[donor_start..donor_end]);
    buf.extend_from_slice(&host[seg_end..]);
}

/// Quick capacity pre-filter: after exchanging segments, the cumulative load
/// at positions outside the exchanged segment shifts by `demand_shift`.
/// Check if any position would exceed capacity.
fn capacity_feasible(
    inst: &Instance,
    route: &[usize],
    seg_start: usize,
    seg_end: usize,
    demand_shift: i32,
) -> bool {
    if demand_shift == 0 {
        return true;
    }
    // Positions after the segment (seg_end..len-1) see a cumulative shift
    let mut load: i32 = 0;
    for (i, &node) in route.iter().enumerate().skip(1).take(route.len() - 2) {
        if i >= seg_start && i < seg_end {
            continue; // segment being replaced, skip
        }
        // Load contribution from remaining nodes
        load += inst.demand[node];
        // After the segment, the cumulative load is shifted
        let effective_load = if i >= seg_end {
            load + demand_shift
        } else {
            load
        };
        if effective_load > inst.capacity || effective_load < 0 {
            return false;
        }
    }
    true
}

/// Precedence pre-filter for segment exchange.
/// For a valid exchange, every PD pair must remain intact:
/// - If pickup is in seg1 of r1, its delivery must be in seg1 of r1 OR in seg2 of r2
///   (because seg1 moves from r1 to r2, replacing seg2)
/// - Similarly for seg2
/// - If pickup is outside both segments, delivery must also be outside (in same route)
fn precedence_feasible_exchange(
    inst: &Instance,
    r1: &[usize],
    s1_start: usize,
    s1_end: usize,
    pos1: &[usize],
    r2: &[usize],
    s2_start: usize,
    s2_end: usize,
    pos2: &[usize],
) -> bool {
    // Check r1: pickup and delivery of each pair must both be in seg1 or both outside
    if !segment_pairs_intact(inst, r1, s1_start, s1_end, pos1) {
        return false;
    }
    // Check r2: same for seg2
    if !segment_pairs_intact(inst, r2, s2_start, s2_end, pos2) {
        return false;
    }
    true
}

/// Check that no PD pair is split by the segment boundary.
/// Only iterates nodes inside the segment with O(1) position lookups
/// via precomputed pos array (subroute feasibility caching).
fn segment_pairs_intact(
    inst: &Instance,
    route: &[usize],
    seg_start: usize,
    seg_end: usize,
    pos: &[usize],
) -> bool {
    for &v in route.iter().take(seg_end).skip(seg_start) {
        if v == 0 {
            continue;
        }
        let partner = if inst.is_pickup(v) {
            inst.delivery_of(v)
        } else {
            inst.pickup_of(v)
        };
        if partner == 0 {
            continue;
        }
        let pp = pos[partner];
        if pp == usize::MAX {
            continue; // partner in a different route
        }
        if pp < seg_start || pp >= seg_end {
            return false; // pair split by segment boundary
        }
    }
    true
}

/// Check full route feasibility: capacity, time windows, and precedence.
/// Uses precomputed RouteInfo for arrival times and loads.
fn is_route_feasible_full(inst: &Instance, route: &[usize], info: &RouteInfo) -> bool {
    // Capacity check
    for i in 1..route.len() - 1 {
        if info.load[i] > inst.capacity || info.load[i] < 0 {
            return false;
        }
    }
    // Time window check
    for (i, &node) in route.iter().enumerate() {
        if info.arrival[i] > inst.late(node) + 1e-10 {
            return false;
        }
    }
    // Precedence check: every pickup must appear before its delivery
    let mut seen_pickup = vec![false; inst.n + 1];
    for &v in &route[1..route.len() - 1] {
        if inst.is_pickup(v) {
            seen_pickup[v] = true;
        } else {
            let p = inst.pickup_of(v);
            if p > 0 && !seen_pickup[p] {
                return false;
            }
        }
    }
    true
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::instance::tests::make_test_instance;
    use crate::solution::{RouteInfo, compute_all_infos, is_route_feasible, route_distance};

    // ---------------------------------------------------------------
    //  Test instance factories
    // ---------------------------------------------------------------

    /// 2 PD pairs, wide TW, unit distances on a line: 0-1-2-3-4
    /// Pairs: (1,3), (2,4).  demand: 0,+1,+1,-1,-1
    fn inst_2pairs() -> Instance {
        let total = 5; // nodes 0..4
        let mut dist = vec![0.0; total * total];
        for i in 0..total {
            for j in 0..total {
                dist[i * total + j] = (i as f64 - j as f64).abs();
            }
        }
        make_test_instance(
            2,  // m = 2 pairs
            10, // capacity
            &dist,
            &[0, 1, 1, -1, -1],
            &[0.0, 0.0, 0.0, 0.0, 0.0],
            &[100.0, 100.0, 100.0, 100.0, 100.0],
            &[0.0; 5],
        )
    }

    /// 3 PD pairs for richer exchange tests.
    /// Pairs: (1,4), (2,5), (3,6).
    fn inst_3pairs() -> Instance {
        let total = 7;
        let mut dist = vec![0.0; total * total];
        for i in 0..total {
            for j in 0..total {
                dist[i * total + j] = (i as f64 - j as f64).abs();
            }
        }
        make_test_instance(
            3,
            20,
            &dist,
            &[0, 1, 1, 1, -1, -1, -1],
            &[0.0; 7],
            &[100.0; 7],
            &[0.0; 7],
        )
    }

    /// 4 PD pairs, carefully positioned to make exchange beneficial.
    /// Pairs: (1,5), (2,6), (3,7), (4,8).
    fn inst_4pairs_for_exchange() -> Instance {
        let total = 9; // 0=depot, 1-4 pickups, 5-8 deliveries
        let coords: [(f64, f64); 9] = [
            (5.0, 0.0),  // 0: depot
            (0.0, 2.0),  // 1: p1
            (10.0, 2.0), // 2: p2
            (10.0, 0.0), // 3: p3
            (0.0, 0.5),  // 4: p4
            (0.0, 3.0),  // 5: d1
            (10.0, 3.0), // 6: d2
            (10.0, 1.0), // 7: d3
            (0.0, 1.0),  // 8: d4
        ];
        let mut dist = vec![0.0; total * total];
        for i in 0..total {
            for j in 0..total {
                let dx = coords[i].0 - coords[j].0;
                let dy = coords[i].1 - coords[j].1;
                dist[i * total + j] = (dx * dx + dy * dy).sqrt();
            }
        }
        make_test_instance(
            4,
            20,
            &dist,
            &[0, 1, 1, 1, 1, -1, -1, -1, -1],
            &[0.0; 9],
            &[1000.0; 9],
            &[0.0; 9],
        )
    }

    // ---------------------------------------------------------------
    //  Unit tests: build_exchanged_route
    // ---------------------------------------------------------------

    #[test]
    fn build_exchanged_route_same_size() {
        let host = vec![0, 10, 20, 30, 0];
        let donor = vec![0, 40, 50, 60, 0];
        let mut buf = Vec::new();
        build_exchanged_route(&host, 1, 2, &donor, 2, 3, &mut buf);
        assert_eq!(buf, vec![0, 50, 20, 30, 0]);
    }

    #[test]
    fn build_exchanged_route_different_sizes() {
        let host = vec![0, 10, 20, 30, 0];
        let donor = vec![0, 40, 50, 0];
        let mut buf = Vec::new();
        build_exchanged_route(&host, 1, 3, &donor, 1, 2, &mut buf);
        assert_eq!(buf, vec![0, 40, 30, 0]);
    }

    #[test]
    fn build_exchanged_route_full_inner() {
        let host = vec![0, 10, 20, 0];
        let donor = vec![0, 30, 40, 50, 0];
        let mut buf = Vec::new();
        build_exchanged_route(&host, 1, 3, &donor, 1, 4, &mut buf);
        assert_eq!(buf, vec![0, 30, 40, 50, 0]);
    }

    // ---------------------------------------------------------------
    //  Test helpers
    // ---------------------------------------------------------------

    fn make_pos(inst: &Instance, route: &[usize]) -> Vec<usize> {
        let mut pos = vec![usize::MAX; inst.n + 1];
        for (idx, &v) in route.iter().enumerate() {
            if v != 0 && v <= inst.n {
                pos[v] = idx;
            }
        }
        pos
    }

    // ---------------------------------------------------------------
    //  Unit tests: segment_pairs_intact
    // ---------------------------------------------------------------

    #[test]
    fn pairs_intact_both_in_segment() {
        let inst = inst_2pairs();
        let route = vec![0, 1, 3, 2, 4, 0]; // pair(1,3) then pair(2,4)
        let pos = make_pos(&inst, &route);
        assert!(segment_pairs_intact(&inst, &route, 1, 3, &pos));
    }

    #[test]
    fn pairs_intact_both_outside_segment() {
        let inst = inst_2pairs();
        let route = vec![0, 1, 3, 2, 4, 0];
        let pos = make_pos(&inst, &route);
        assert!(segment_pairs_intact(&inst, &route, 3, 5, &pos));
    }

    #[test]
    fn pairs_split_pickup_in_delivery_out() {
        let inst = inst_2pairs();
        let route = vec![0, 1, 3, 2, 4, 0];
        let pos = make_pos(&inst, &route);
        assert!(!segment_pairs_intact(&inst, &route, 1, 2, &pos));
    }

    #[test]
    fn pairs_split_pickup_out_delivery_in() {
        let inst = inst_2pairs();
        let route = vec![0, 1, 3, 2, 4, 0];
        let pos = make_pos(&inst, &route);
        // Pickup 1 at pos 1 (outside [2,3)), delivery 3 at pos 2 (inside) → split
        assert!(!segment_pairs_intact(&inst, &route, 2, 3, &pos));
    }

    #[test]
    fn pairs_intact_single_pair_route() {
        let inst = inst_2pairs();
        let route = vec![0, 1, 3, 0];
        let pos = make_pos(&inst, &route);
        assert!(segment_pairs_intact(&inst, &route, 1, 3, &pos));
    }

    // ---------------------------------------------------------------
    //  Unit tests: capacity_feasible
    // ---------------------------------------------------------------

    #[test]
    fn capacity_feasible_zero_shift() {
        let inst = inst_2pairs();
        let route = vec![0, 1, 3, 2, 4, 0];
        assert!(capacity_feasible(&inst, &route, 1, 3, 0));
    }

    #[test]
    fn capacity_feasible_positive_shift_ok() {
        let inst = inst_2pairs(); // capacity = 10
        let route = vec![0, 1, 3, 2, 4, 0];
        assert!(capacity_feasible(&inst, &route, 1, 3, 5));
    }

    #[test]
    fn capacity_feasible_positive_shift_overflow() {
        let inst = inst_2pairs(); // capacity = 10
        let route = vec![0, 1, 3, 2, 4, 0];
        assert!(!capacity_feasible(&inst, &route, 1, 3, 10));
    }

    #[test]
    fn capacity_feasible_negative_shift() {
        let inst = inst_2pairs(); // capacity = 10
        let route = vec![0, 1, 3, 2, 4, 0];
        assert!(!capacity_feasible(&inst, &route, 1, 3, -5));
    }

    // ---------------------------------------------------------------
    //  Unit tests: precedence_feasible_exchange
    // ---------------------------------------------------------------

    #[test]
    fn precedence_exchange_valid_full_pairs() {
        let inst = inst_2pairs();
        let r1 = vec![0, 1, 3, 0];
        let r2 = vec![0, 2, 4, 0];
        let pos1 = make_pos(&inst, &r1);
        let pos2 = make_pos(&inst, &r2);
        assert!(precedence_feasible_exchange(
            &inst, &r1, 1, 3, &pos1, &r2, 1, 3, &pos2
        ));
    }

    #[test]
    fn precedence_exchange_invalid_split_pair() {
        let inst = inst_3pairs();
        let r1 = vec![0, 1, 2, 4, 5, 0];
        let r2 = vec![0, 3, 6, 0];
        let pos1 = make_pos(&inst, &r1);
        let pos2 = make_pos(&inst, &r2);
        assert!(!precedence_feasible_exchange(
            &inst, &r1, 1, 3, &pos1, &r2, 1, 3, &pos2
        ));
    }

    // ---------------------------------------------------------------
    //  Unit tests: is_route_feasible_full
    // ---------------------------------------------------------------

    #[test]
    fn route_feasible_full_valid() {
        let inst = inst_2pairs();
        let route = vec![0, 1, 3, 2, 4, 0];
        let mut info = RouteInfo::new();
        info.compute(&inst, &route);
        assert!(is_route_feasible_full(&inst, &route, &info));
    }

    #[test]
    fn route_feasible_full_matches_is_route_feasible() {
        let inst = inst_3pairs();
        let routes = vec![
            vec![0, 1, 4, 2, 5, 3, 6, 0],
            vec![0, 1, 2, 3, 4, 5, 6, 0],
            vec![0, 4, 1, 2, 5, 3, 6, 0], // delivery 4 before pickup 1
            vec![0, 1, 2, 5, 4, 3, 6, 0],
        ];
        let mut info = RouteInfo::new();
        for route in &routes {
            info.compute(&inst, route);
            assert_eq!(
                is_route_feasible_full(&inst, route, &info),
                is_route_feasible(&inst, route),
                "Mismatch for route {route:?}"
            );
        }
    }

    // ---------------------------------------------------------------
    //  Unit tests: apply_segment_exchange
    // ---------------------------------------------------------------

    #[test]
    fn exchange_single_route_returns_false() {
        let inst = inst_2pairs();
        let mut routes = vec![vec![0, 1, 3, 2, 4, 0]];
        let mut infos = Vec::new();
        compute_all_infos(&inst, &routes, &mut infos);
        assert!(!apply_segment_exchange(&inst, &mut routes, &mut infos));
    }

    #[test]
    fn exchange_preserves_feasibility() {
        let inst = inst_4pairs_for_exchange();
        let mut routes = vec![vec![0, 1, 5, 4, 8, 0], vec![0, 3, 7, 2, 6, 0]];
        let mut infos = Vec::new();
        compute_all_infos(&inst, &routes, &mut infos);

        assert!(is_route_feasible(&inst, &routes[0]));
        assert!(is_route_feasible(&inst, &routes[1]));

        let initial_dist: f64 = routes.iter().map(|r| route_distance(&inst, r)).sum();

        while apply_segment_exchange(&inst, &mut routes, &mut infos) {
            for (i, route) in routes.iter().enumerate() {
                assert!(
                    is_route_feasible(&inst, route),
                    "Route {i} infeasible after exchange: {route:?}"
                );
            }
        }

        let final_dist: f64 = routes.iter().map(|r| route_distance(&inst, r)).sum();
        assert!(final_dist <= initial_dist + 1e-9);
    }

    #[test]
    fn exchange_finds_improving_swap() {
        let inst = inst_4pairs_for_exchange();
        let mut routes = vec![vec![0, 2, 6, 4, 8, 0], vec![0, 1, 5, 3, 7, 0]];
        let mut infos = Vec::new();
        compute_all_infos(&inst, &routes, &mut infos);
        let dist_before: f64 = routes.iter().map(|r| route_distance(&inst, r)).sum();

        let improved = apply_segment_exchange(&inst, &mut routes, &mut infos);

        if improved {
            let dist_after: f64 = routes.iter().map(|r| route_distance(&inst, r)).sum();
            assert!(dist_after < dist_before - 1e-10);
            for route in &routes {
                assert!(is_route_feasible(&inst, route));
            }
        }
    }

    #[test]
    fn exchange_tight_tw_rejects_infeasible() {
        let total = 5;
        let mut dist = vec![0.0; total * total];
        for i in 0..total {
            for j in 0..total {
                dist[i * total + j] = (i as f64 - j as f64).abs();
            }
        }
        let inst = make_test_instance(
            2,
            10,
            &dist,
            &[0, 1, 1, -1, -1],
            &[0.0, 1.0, 1.0, 3.0, 3.0],
            &[100.0, 1.5, 1.5, 3.5, 3.5],
            &[0.0; 5],
        );
        let mut routes = vec![vec![0, 1, 3, 0], vec![0, 2, 4, 0]];
        let mut infos = Vec::new();
        compute_all_infos(&inst, &routes, &mut infos);

        while apply_segment_exchange(&inst, &mut routes, &mut infos) {
            for route in &routes {
                assert!(is_route_feasible(&inst, route));
            }
        }
    }

    #[test]
    fn exchange_capacity_constraint_respected() {
        let total = 5;
        let mut dist = vec![0.0; total * total];
        for i in 0..total {
            for j in 0..total {
                dist[i * total + j] = (i as f64 - j as f64).abs();
            }
        }
        let inst = make_test_instance(
            2,
            1,
            &dist,
            &[0, 1, 1, -1, -1],
            &[0.0; 5],
            &[100.0; 5],
            &[0.0; 5],
        );
        let mut routes = vec![vec![0, 1, 3, 0], vec![0, 2, 4, 0]];
        let mut infos = Vec::new();
        compute_all_infos(&inst, &routes, &mut infos);

        while apply_segment_exchange(&inst, &mut routes, &mut infos) {
            for route in &routes {
                assert!(is_route_feasible(&inst, route));
            }
        }
    }

    // ---------------------------------------------------------------
    //  Capacity pre-filter is dead when precedence passes
    // ---------------------------------------------------------------

    #[test]
    fn capacity_prefilter_always_zero_shift_after_precedence() {
        let inst = inst_3pairs();
        let r1 = vec![0, 1, 4, 2, 5, 0];
        let r2 = vec![0, 3, 6, 0];
        let pos1 = make_pos(&inst, &r1);
        let pos2 = make_pos(&inst, &r2);

        for s1_start in 1..r1.len() - 1 {
            for s1_len in 1..=3usize {
                let s1_end = s1_start + s1_len;
                if s1_end > r1.len() - 1 {
                    break;
                }
                if !segment_pairs_intact(&inst, &r1, s1_start, s1_end, &pos1) {
                    continue;
                }
                let seg_demand: i32 = r1[s1_start..s1_end].iter().map(|&v| inst.demand[v]).sum();
                assert_eq!(
                    seg_demand, 0,
                    "Non-zero demand for intact segment r1[{s1_start}..{s1_end})"
                );
            }
        }
        for s2_start in 1..r2.len() - 1 {
            for s2_len in 1..=3usize {
                let s2_end = s2_start + s2_len;
                if s2_end > r2.len() - 1 {
                    break;
                }
                if !segment_pairs_intact(&inst, &r2, s2_start, s2_end, &pos2) {
                    continue;
                }
                let seg_demand: i32 = r2[s2_start..s2_end].iter().map(|&v| inst.demand[v]).sum();
                assert_eq!(
                    seg_demand, 0,
                    "Non-zero demand for intact segment r2[{s2_start}..{s2_end})"
                );
            }
        }
    }

    // ---------------------------------------------------------------
    //  Distance delta correctness
    // ---------------------------------------------------------------

    #[test]
    fn distance_delta_matches_actual() {
        let inst = inst_3pairs();
        let r1 = vec![0, 1, 4, 2, 5, 0];
        let r2 = vec![0, 3, 6, 0];
        let base_dist = route_distance(&inst, &r1) + route_distance(&inst, &r2);

        for s1_start in 1..r1.len() - 1 {
            for s1_len in 1..=3usize {
                let s1_end = s1_start + s1_len;
                if s1_end > r1.len() - 1 {
                    break;
                }
                let r1_before = r1[s1_start - 1];
                let r1_after = r1[s1_end];
                let r1_removed =
                    inst.dist(r1_before, r1[s1_start]) + inst.dist(r1[s1_end - 1], r1_after);

                for s2_start in 1..r2.len() - 1 {
                    for s2_len in 1..=3usize {
                        let s2_end = s2_start + s2_len;
                        if s2_end > r2.len() - 1 {
                            break;
                        }
                        let r2_before = r2[s2_start - 1];
                        let r2_after = r2[s2_end];
                        let r2_removed = inst.dist(r2_before, r2[s2_start])
                            + inst.dist(r2[s2_end - 1], r2_after);
                        let r1_new_edges = inst.dist(r1_before, r2[s2_start])
                            + inst.dist(r2[s2_end - 1], r1_after);
                        let r2_new_edges = inst.dist(r2_before, r1[s1_start])
                            + inst.dist(r1[s1_end - 1], r2_after);
                        let delta = (r1_new_edges - r1_removed) + (r2_new_edges - r2_removed);

                        let mut new_r1 = Vec::new();
                        let mut new_r2 = Vec::new();
                        build_exchanged_route(
                            &r1,
                            s1_start,
                            s1_end,
                            &r2,
                            s2_start,
                            s2_end,
                            &mut new_r1,
                        );
                        build_exchanged_route(
                            &r2,
                            s2_start,
                            s2_end,
                            &r1,
                            s1_start,
                            s1_end,
                            &mut new_r2,
                        );
                        let actual_dist =
                            route_distance(&inst, &new_r1) + route_distance(&inst, &new_r2);
                        let actual_delta = actual_dist - base_dist;

                        assert!(
                            (delta - actual_delta).abs() < 1e-9,
                            "Delta mismatch at s1=[{s1_start},{s1_end}), s2=[{s2_start},{s2_end}): computed={delta:.6}, actual={actual_delta:.6}",
                        );
                    }
                }
            }
        }
    }
}

#[cfg(test)]
mod proptest_tests {
    use super::*;
    use crate::instance::tests::make_test_instance;
    use crate::solution::{compute_all_infos, is_route_feasible, route_distance};
    use proptest::prelude::*;

    proptest! {
        #![proptest_config(ProptestConfig::with_cases(200))]

        #[test]
        fn exchange_always_preserves_feasibility(
            m in 2..6usize,
            split in 1..5usize,
        ) {
            let split = (split % (m - 1)) + 1;
            let total = 2 * m + 1;
            let mut dist = vec![0.0; total * total];
            for i in 0..total {
                for j in 0..total {
                    dist[i * total + j] = (i as f64 - j as f64).abs();
                }
            }
            let demand: Vec<i32> = (0..total)
                .map(|i| if i == 0 { 0 } else if i <= m { 1 } else { -1 })
                .collect();
            let inst = make_test_instance(
                m, 100, &dist, &demand,
                &vec![0.0; total], &vec![1000.0; total], &vec![0.0; total],
            );

            let mut r1 = vec![0];
            let mut r2 = vec![0];
            for i in 1..=m {
                if i <= split { r1.push(i); r1.push(m + i); }
                else { r2.push(i); r2.push(m + i); }
            }
            r1.push(0);
            r2.push(0);

            prop_assert!(is_route_feasible(&inst, &r1));
            prop_assert!(is_route_feasible(&inst, &r2));

            let mut routes = vec![r1, r2];
            let mut infos = Vec::new();
            compute_all_infos(&inst, &routes, &mut infos);

            let mut iterations = 0;
            while apply_segment_exchange(&inst, &mut routes, &mut infos) {
                for (i, r) in routes.iter().enumerate() {
                    prop_assert!(is_route_feasible(&inst, r),
                        "Route {} infeasible after iter {}: {:?}", i, iterations, r);
                }
                iterations += 1;
                if iterations > 100 { break; }
            }
        }

        #[test]
        fn exchange_never_increases_distance(
            m in 2..6usize,
            split in 1..5usize,
        ) {
            let split = (split % (m - 1)) + 1;
            let total = 2 * m + 1;
            let mut dist = vec![0.0; total * total];
            for i in 0..total {
                for j in 0..total {
                    dist[i * total + j] = (i as f64 - j as f64).abs();
                }
            }
            let demand: Vec<i32> = (0..total)
                .map(|i| if i == 0 { 0 } else if i <= m { 1 } else { -1 })
                .collect();
            let inst = make_test_instance(
                m, 100, &dist, &demand,
                &vec![0.0; total], &vec![1000.0; total], &vec![0.0; total],
            );

            let mut r1 = vec![0];
            let mut r2 = vec![0];
            for i in 1..=m {
                if i <= split { r1.push(i); r1.push(m + i); }
                else { r2.push(i); r2.push(m + i); }
            }
            r1.push(0);
            r2.push(0);

            let mut routes = vec![r1, r2];
            let mut infos = Vec::new();
            compute_all_infos(&inst, &routes, &mut infos);
            let initial_dist: f64 = routes.iter().map(|r| route_distance(&inst, r)).sum();

            let mut iters = 0;
            while apply_segment_exchange(&inst, &mut routes, &mut infos) {
                iters += 1;
                if iters > 100 { break; }
            }

            let final_dist: f64 = routes.iter().map(|r| route_distance(&inst, r)).sum();
            prop_assert!(final_dist <= initial_dist + 1e-9,
                "Distance increased: {:.4} -> {:.4}", initial_dist, final_dist);
        }

        #[test]
        fn build_exchanged_route_preserves_total_nodes(
            host_inner in prop::collection::vec(1..100usize, 1..8),
            donor_inner in prop::collection::vec(1..100usize, 1..8),
            seg_offset1 in 0..7usize,
            seg_len1 in 1..4usize,
            seg_offset2 in 0..7usize,
            seg_len2 in 1..4usize,
        ) {
            let host: Vec<usize> = std::iter::once(0)
                .chain(host_inner.iter().copied())
                .chain(std::iter::once(0))
                .collect();
            let donor: Vec<usize> = std::iter::once(0)
                .chain(donor_inner.iter().copied())
                .chain(std::iter::once(0))
                .collect();

            let h_inner = host.len() - 2;
            let d_inner = donor.len() - 2;
            if h_inner == 0 || d_inner == 0 { return Ok(()); }

            let s1_start = 1 + (seg_offset1 % h_inner);
            let s1_len = std::cmp::min(seg_len1, h_inner - (s1_start - 1));
            let s1_end = s1_start + s1_len;
            if s1_end > host.len() - 1 { return Ok(()); }

            let s2_start = 1 + (seg_offset2 % d_inner);
            let s2_len = std::cmp::min(seg_len2, d_inner - (s2_start - 1));
            let s2_end = s2_start + s2_len;
            if s2_end > donor.len() - 1 { return Ok(()); }

            let mut buf = Vec::new();
            build_exchanged_route(&host, s1_start, s1_end, &donor, s2_start, s2_end, &mut buf);

            let expected_len = host.len() - (s1_end - s1_start) + (s2_end - s2_start);
            prop_assert_eq!(buf.len(), expected_len);
            prop_assert_eq!(buf[0], 0);
            prop_assert_eq!(buf[buf.len() - 1], 0);
        }

        #[test]
        fn segment_pairs_intact_complete_pairs_have_zero_demand(m in 2..6usize) {
            let total = 2 * m + 1;
            let mut dist = vec![0.0; total * total];
            for i in 0..total { for j in 0..total { dist[i*total+j] = 1.0; } }
            let demand: Vec<i32> = (0..total)
                .map(|i| if i == 0 { 0 } else if i <= m { 1 } else { -1 })
                .collect();
            let inst = make_test_instance(
                m, 100, &dist, &demand,
                &vec![0.0; total], &vec![1000.0; total], &vec![0.0; total],
            );

            let mut route = vec![0];
            for i in 1..=m { route.push(i); route.push(m + i); }
            route.push(0);

            let mut pos = vec![usize::MAX; inst.n + 1];
            for (idx, &v) in route.iter().enumerate() {
                if v != 0 && v <= inst.n { pos[v] = idx; }
            }

            for seg_start in 1..route.len() - 1 {
                for seg_len in 1..=std::cmp::min(MAX_SEG, route.len() - 1 - seg_start) {
                    let seg_end = seg_start + seg_len;
                    if seg_end > route.len() - 1 { break; }
                    if segment_pairs_intact(&inst, &route, seg_start, seg_end, &pos) {
                        let seg_demand: i32 = route[seg_start..seg_end].iter()
                            .map(|&v| inst.demand[v]).sum();
                        prop_assert_eq!(seg_demand, 0,
                            "Intact seg [{},{}) in {:?} has demand {}",
                            seg_start, seg_end, route, seg_demand);
                    }
                }
            }
        }
    }
}