ftui-extras 0.4.0

//! Sugiyama-based graph layout engine for Mermaid diagrams.
//!
//! Produces positioned nodes, edges, clusters, and ports in world-unit f64
//! coordinates. The engine is fully deterministic: same input always produces
//! identical output with no RNG or floating-point non-determinism.
//!
//! # Pipeline
//! 1. Cycle removal (greedy source/sink peeling)
//! 2. Layer assignment (longest-path via topological sort)
//! 3. Crossing minimization (barycenter heuristic)
//! 4. Coordinate assignment (median refinement)
//! 5. Post-processing: cluster boxes, port resolution, edge routing, quality scoring

use crate::mermaid::{
    GraphDirection, IrClusterId, IrEndpoint, IrNodeId, IrPortId, IrPortSideHint, MermaidDiagramIr,
};

// ---------------------------------------------------------------------------
// Output types
// ---------------------------------------------------------------------------

/// Which side of a node a port attaches to.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PortSide {
    Top,
    Bottom,
    Left,
    Right,
}

/// A positioned node in world coordinates.
#[derive(Debug, Clone)]
pub struct NodeBox {
    pub ir_node: IrNodeId,
    pub cx: f64,
    pub cy: f64,
    pub width: f64,
    pub height: f64,
}

impl NodeBox {
    #[must_use]
    pub fn left(&self) -> f64 {
        self.cx - self.width / 2.0
    }
    #[must_use]
    pub fn right(&self) -> f64 {
        self.cx + self.width / 2.0
    }
    #[must_use]
    pub fn top(&self) -> f64 {
        self.cy - self.height / 2.0
    }
    #[must_use]
    pub fn bottom(&self) -> f64 {
        self.cy + self.height / 2.0
    }

    #[cfg(test)]
    fn overlaps(&self, other: &NodeBox) -> bool {
        self.left() < other.right()
            && self.right() > other.left()
            && self.top() < other.bottom()
            && self.bottom() > other.top()
    }
}

/// A positioned subgraph bounding box.
#[derive(Debug, Clone)]
pub struct ClusterBox {
    pub ir_cluster: IrClusterId,
    pub x: f64,
    pub y: f64,
    pub width: f64,
    pub height: f64,
    pub padding: f64,
}

/// A positioned port attachment point.
#[derive(Debug, Clone)]
pub struct PortPoint {
    pub ir_port: IrPortId,
    pub ir_node: IrNodeId,
    pub x: f64,
    pub y: f64,
    pub side: PortSide,
}

/// A routed edge as a polyline.
#[derive(Debug, Clone)]
pub struct RoutedEdge {
    pub ir_edge_idx: usize,
    pub from: IrNodeId,
    pub to: IrNodeId,
    pub waypoints: Vec<(f64, f64)>,
    pub reversed: bool,
}

/// Routing channel information for future orthogonal routing.
#[derive(Debug, Clone, Default)]
pub struct RouteGrid {
    pub vertical_channels: Vec<f64>,
    pub horizontal_channels: Vec<f64>,
}

/// Quality metrics for a layout.
#[derive(Debug, Clone)]
pub struct LayoutQuality {
    pub crossings: usize,
    pub bends: usize,
    pub variance: f64,
    pub asymmetry: f64,
    pub total_score: f64,
}

/// Complete layout result.
#[derive(Debug, Clone)]
pub struct DiagramLayout {
    pub nodes: Vec<NodeBox>,
    pub clusters: Vec<ClusterBox>,
    pub ports: Vec<PortPoint>,
    pub edges: Vec<RoutedEdge>,
    pub route_grid: RouteGrid,
    pub bounds: (f64, f64, f64, f64),
    pub quality: LayoutQuality,
    pub degraded: bool,
}

/// Configuration knobs for the layout engine.
#[derive(Debug, Clone)]
pub struct LayoutConfig {
    pub node_width: f64,
    pub node_height: f64,
    pub node_spacing: f64,
    pub layer_spacing: f64,
    pub cluster_padding: f64,
    pub max_crossing_iterations: usize,
    pub iteration_budget: usize,
    pub collapse_clusters: bool,
}

impl Default for LayoutConfig {
    fn default() -> Self {
        Self {
            node_width: 80.0,
            node_height: 40.0,
            node_spacing: 30.0,
            layer_spacing: 60.0,
            cluster_padding: 10.0,
            max_crossing_iterations: 24,
            iteration_budget: 10_000,
            collapse_clusters: false,
        }
    }
}

impl LayoutConfig {
    /// Build config from IR guard report, respecting degradation hints.
    #[must_use]
    pub fn from_ir(ir: &MermaidDiagramIr) -> Self {
        let mut config = Self::default();
        let guard = &ir.meta.guard;
        if guard.layout_budget_exceeded {
            config.max_crossing_iterations = 4;
            config.iteration_budget = 2_000;
        }
        if guard.degradation.collapse_clusters {
            config.collapse_clusters = true;
        }
        config
    }
}

// ---------------------------------------------------------------------------
// Internal graph representation
// ---------------------------------------------------------------------------

struct LayoutGraph {
    num_nodes: usize,
    adj: Vec<Vec<usize>>,
    radj: Vec<Vec<usize>>,
    node_widths: Vec<f64>,
    node_heights: Vec<f64>,
    cluster_members: Vec<(IrClusterId, Vec<usize>)>,
}

impl LayoutGraph {
    fn from_ir(ir: &MermaidDiagramIr, config: &LayoutConfig) -> Self {
        let num_nodes = ir.nodes.len();
        let mut adj = vec![Vec::new(); num_nodes];
        let mut radj = vec![Vec::new(); num_nodes];

        for edge in &ir.edges {
            let Some(from) = resolve_node(ir, edge.from, num_nodes) else {
                continue;
            };
            let Some(to) = resolve_node(ir, edge.to, num_nodes) else {
                continue;
            };
            if from == to {
                continue;
            }
            adj[from].push(to);
            radj[to].push(from);
        }

        let node_widths = vec![config.node_width; num_nodes];
        let node_heights = vec![config.node_height; num_nodes];

        let cluster_members: Vec<(IrClusterId, Vec<usize>)> = ir
            .clusters
            .iter()
            .map(|c| (c.id, c.members.iter().map(|id| id.0).collect()))
            .collect();

        Self {
            num_nodes,
            adj,
            radj,
            node_widths,
            node_heights,
            cluster_members,
        }
    }
}

fn resolve_node(ir: &MermaidDiagramIr, endpoint: IrEndpoint, num_nodes: usize) -> Option<usize> {
    let idx = match endpoint {
        IrEndpoint::Node(id) => id.0,
        IrEndpoint::Port(pid) => ir.ports.get(pid.0)?.node.0,
    };
    if idx < num_nodes { Some(idx) } else { None }
}

// ---------------------------------------------------------------------------
// Cycle removal tracking
// ---------------------------------------------------------------------------

struct CycleRemoval {
    reversed: Vec<(usize, usize)>,
}

// ---------------------------------------------------------------------------
// Phase 1: Cycle removal — greedy source/sink peeling
// ---------------------------------------------------------------------------

fn remove_cycles(graph: &mut LayoutGraph, budget: &mut usize) -> CycleRemoval {
    let n = graph.num_nodes;
    let mut in_deg = vec![0usize; n];
    let mut out_deg = vec![0usize; n];
    let mut removed = vec![false; n];

    for (u, adj) in graph.adj.iter().enumerate() {
        for &v in adj {
            if u != v {
                out_deg[u] += 1;
                in_deg[v] += 1;
            }
        }
    }

    let mut left_order: Vec<usize> = Vec::new();
    let mut right_order: Vec<usize> = Vec::new();
    let mut remaining = n;

    while remaining > 0 && *budget > 0 {
        *budget = budget.saturating_sub(1);
        let mut progress = false;

        // Remove sinks (out_deg == 0)
        for v in 0..n {
            if !removed[v] && out_deg[v] == 0 {
                removed[v] = true;
                remaining -= 1;
                right_order.push(v);
                for &u in &graph.radj[v] {
                    if !removed[u] && u != v {
                        out_deg[u] = out_deg[u].saturating_sub(1);
                    }
                }
                progress = true;
            }
        }

        // Remove sources (in_deg == 0)
        for v in 0..n {
            if !removed[v] && in_deg[v] == 0 {
                removed[v] = true;
                remaining -= 1;
                left_order.push(v);
                for &w in &graph.adj[v] {
                    if !removed[w] && w != v {
                        in_deg[w] = in_deg[w].saturating_sub(1);
                    }
                }
                progress = true;
            }
        }

        if !progress && remaining > 0 {
            // Pick node with max (out_deg - in_deg), tiebreak by index
            let best = (0..n).filter(|&v| !removed[v]).max_by(|&a, &b| {
                let da = out_deg[a] as isize - in_deg[a] as isize;
                let db = out_deg[b] as isize - in_deg[b] as isize;
                da.cmp(&db).then_with(|| b.cmp(&a))
            });
            if let Some(v) = best {
                removed[v] = true;
                remaining -= 1;
                left_order.push(v);
                for &w in &graph.adj[v] {
                    if !removed[w] && w != v {
                        in_deg[w] = in_deg[w].saturating_sub(1);
                    }
                }
                for &u in &graph.radj[v] {
                    if !removed[u] && u != v {
                        out_deg[u] = out_deg[u].saturating_sub(1);
                    }
                }
            }
        }
    }

    // Build final ordering (must include all nodes for a total order).
    right_order.reverse();
    left_order.extend(right_order);
    if left_order.len() < n {
        for (v, is_removed) in removed.iter().enumerate().take(n) {
            if !is_removed {
                left_order.push(v);
            }
        }
    }
    let order = left_order;

    let mut pos = vec![0usize; n];
    for (i, &v) in order.iter().enumerate() {
        pos[v] = i;
    }

    // Collect original edges, classify as kept or reversed, rebuild adj/radj
    let mut reversed = Vec::new();
    let mut new_adj = vec![Vec::new(); n];
    let mut new_radj = vec![Vec::new(); n];

    for u in 0..n {
        for &v in &graph.adj[u] {
            if u == v {
                continue; // remove self-loops
            }
            if pos[u] > pos[v] {
                // Reverse this edge: was u->v, now v->u
                reversed.push((u, v));
                new_adj[v].push(u);
                new_radj[u].push(v);
            } else {
                new_adj[u].push(v);
                new_radj[v].push(u);
            }
        }
    }

    graph.adj = new_adj;
    graph.radj = new_radj;

    CycleRemoval { reversed }
}

// ---------------------------------------------------------------------------
// Phase 2: Layer assignment — longest-path via topological sort
// ---------------------------------------------------------------------------

fn assign_layers(graph: &LayoutGraph, budget: &mut usize) -> Vec<usize> {
    use std::cmp::Reverse;
    use std::collections::BinaryHeap;

    let n = graph.num_nodes;
    if n == 0 {
        return Vec::new();
    }

    let mut in_deg = vec![0usize; n];
    for u in 0..n {
        for &v in &graph.adj[u] {
            in_deg[v] += 1;
        }
    }

    // Topological sort (Kahn's algorithm) — BinaryHeap<Reverse> gives
    // O(log n) push/pop with deterministic min-first ordering.
    let mut queue = BinaryHeap::new();
    for (v, &deg) in in_deg.iter().enumerate() {
        if deg == 0 {
            queue.push(Reverse(v));
        }
    }
    let mut topo = Vec::with_capacity(n);
    let mut visited = vec![false; n];

    while let Some(Reverse(u)) = queue.pop() {
        *budget = budget.saturating_sub(1);
        if *budget == 0 {
            break;
        }
        topo.push(u);
        visited[u] = true;
        for &v in &graph.adj[u] {
            in_deg[v] -= 1;
            if in_deg[v] == 0 {
                queue.push(Reverse(v));
            }
        }
    }

    // Add any remaining nodes not yet visited (disconnected or budget-cut)
    for (v, &vis) in visited.iter().enumerate() {
        if !vis {
            topo.push(v);
        }
    }

    // Longest-path layering with convergence loop.
    // A single forward pass suffices for a correct topo order, but if
    // budget exhaustion produced an incomplete sort, iterate until stable.
    // Cap iterations at `n` to prevent infinite loops when residual cycles
    // survive budget-exhausted cycle removal.
    let mut layer = vec![0usize; n];
    let mut changed = true;
    let mut iters = 0;
    while changed && iters < n {
        changed = false;
        iters += 1;
        for &u in &topo {
            for &v in &graph.adj[u] {
                if layer[v] <= layer[u] {
                    layer[v] = layer[u] + 1;
                    changed = true;
                }
            }
        }
    }

    layer
}

// ---------------------------------------------------------------------------
// Phase 3: Crossing minimization — barycenter heuristic + sifting refinement
// ---------------------------------------------------------------------------

fn count_crossings(layers: &[Vec<usize>], adj: &[Vec<usize>]) -> usize {
    let mut crossings = 0;
    for i in 0..layers.len().saturating_sub(1) {
        let layer_a = &layers[i];
        let layer_b = &layers[i + 1];

        // Position map for layer_b (usize::MAX => not present)
        let max_node = layer_b.iter().copied().max().unwrap_or(0) + 1;
        let mut pos_b = vec![usize::MAX; max_node];
        for (p, &v) in layer_b.iter().enumerate() {
            if v < max_node {
                pos_b[v] = p;
            }
        }

        // Collect all edges between layer_a and layer_b as (pos_in_a, pos_in_b).
        // Edges are naturally sorted by pos_in_a since we iterate layer_a in order;
        // ties are broken by adjacency-list order (deterministic).
        let mut edge_pairs: Vec<(usize, usize)> = Vec::new();
        for (pa, &u) in layer_a.iter().enumerate() {
            for &v in &adj[u] {
                if v < max_node {
                    let pos = pos_b[v];
                    if pos != usize::MAX {
                        edge_pairs.push((pa, pos));
                    }
                }
            }
        }

        // Sort by first element (stable sort preserves insertion order for ties),
        // then count inversions in the second-element sequence via merge sort.
        edge_pairs.sort_by(|a, b| a.0.cmp(&b.0).then_with(|| a.1.cmp(&b.1)));
        let mut seq: Vec<usize> = edge_pairs.iter().map(|&(_, b)| b).collect();
        let mut buf = vec![0usize; seq.len()];
        crossings += merge_sort_count_inversions(&mut seq, &mut buf);
    }
    crossings
}

/// Scratch buffers reused across crossing-count operations to avoid
/// per-call heap allocations on the hot path.
struct CrossingScratch {
    pos_b: Vec<usize>,
    edge_pairs: Vec<(usize, usize)>,
    seq: Vec<usize>,
    merge_buf: Vec<usize>,
}

impl CrossingScratch {
    fn new() -> Self {
        Self {
            pos_b: Vec::new(),
            edge_pairs: Vec::new(),
            seq: Vec::new(),
            merge_buf: Vec::new(),
        }
    }
}

/// Count crossings between a single pair of adjacent layers, reusing scratch buffers.
fn count_crossings_pair_with(
    layer_a: &[usize],
    layer_b: &[usize],
    adj: &[Vec<usize>],
    scratch: &mut CrossingScratch,
) -> usize {
    if layer_a.is_empty() || layer_b.is_empty() {
        return 0;
    }
    let max_node = layer_b.iter().copied().max().unwrap_or(0) + 1;

    // Reuse pos_b buffer
    scratch.pos_b.clear();
    scratch.pos_b.resize(max_node, usize::MAX);
    for (p, &v) in layer_b.iter().enumerate() {
        if v < max_node {
            scratch.pos_b[v] = p;
        }
    }

    // Reuse edge_pairs buffer
    scratch.edge_pairs.clear();
    for (pa, &u) in layer_a.iter().enumerate() {
        for &v in &adj[u] {
            if v < max_node {
                let pos = scratch.pos_b[v];
                if pos != usize::MAX {
                    scratch.edge_pairs.push((pa, pos));
                }
            }
        }
    }

    scratch
        .edge_pairs
        .sort_by(|a, b| a.0.cmp(&b.0).then_with(|| a.1.cmp(&b.1)));

    // Reuse seq and merge_buf
    scratch.seq.clear();
    scratch
        .seq
        .extend(scratch.edge_pairs.iter().map(|&(_, b)| b));
    let n = scratch.seq.len();
    if scratch.merge_buf.len() < n {
        scratch.merge_buf.resize(n, 0);
    }
    merge_sort_count_inversions(&mut scratch.seq, &mut scratch.merge_buf)
}

/// Count total crossings across all adjacent layer pairs, reusing scratch buffers.
fn count_crossings_with(
    layers: &[Vec<usize>],
    adj: &[Vec<usize>],
    scratch: &mut CrossingScratch,
) -> usize {
    let mut crossings = 0;
    for i in 0..layers.len().saturating_sub(1) {
        crossings += count_crossings_pair_with(&layers[i], &layers[i + 1], adj, scratch);
    }
    crossings
}

/// Count crossings involving a specific layer, reusing scratch buffers.
fn count_crossings_at_with(
    layers: &[Vec<usize>],
    layer_idx: usize,
    adj: &[Vec<usize>],
    scratch: &mut CrossingScratch,
) -> usize {
    let mut total = 0;
    if layer_idx > 0 {
        total +=
            count_crossings_pair_with(&layers[layer_idx - 1], &layers[layer_idx], adj, scratch);
    }
    if layer_idx + 1 < layers.len() {
        total +=
            count_crossings_pair_with(&layers[layer_idx], &layers[layer_idx + 1], adj, scratch);
    }
    total
}

/// Count inversions in a slice using merge sort. O(n log n).
/// An inversion is a pair (i, j) where i < j but seq[i] > seq[j].
/// `buf` is a pre-allocated scratch buffer at least as large as `seq`.
fn merge_sort_count_inversions(seq: &mut [usize], buf: &mut [usize]) -> usize {
    let n = seq.len();
    if n <= 1 {
        return 0;
    }
    let mid = n / 2;
    let mut count = 0;
    count += merge_sort_count_inversions(&mut seq[..mid], &mut buf[..mid]);
    count += merge_sort_count_inversions(&mut seq[mid..], &mut buf[mid..n]);

    // Merge step: count split inversions using pre-allocated buffer
    buf[..n].copy_from_slice(&seq[..n]);
    let (left, right) = buf[..n].split_at(mid);
    let (mut li, mut ri, mut wi) = (0, 0, 0);
    while li < left.len() && ri < right.len() {
        if left[li] <= right[ri] {
            seq[wi] = left[li];
            li += 1;
        } else {
            count += left.len() - li;
            seq[wi] = right[ri];
            ri += 1;
        }
        wi += 1;
    }
    while li < left.len() {
        seq[wi] = left[li];
        li += 1;
        wi += 1;
    }
    while ri < right.len() {
        seq[wi] = right[ri];
        ri += 1;
        wi += 1;
    }
    count
}

fn minimize_crossings(
    layer_assignment: &[usize],
    adj: &[Vec<usize>],
    radj: &[Vec<usize>],
    num_nodes: usize,
    max_iterations: usize,
    budget: &mut usize,
) -> Vec<Vec<usize>> {
    if num_nodes == 0 {
        return Vec::new();
    }

    let num_layers = layer_assignment.iter().copied().max().unwrap_or(0) + 1;
    let mut layers: Vec<Vec<usize>> = vec![Vec::new(); num_layers];
    for v in 0..num_nodes {
        layers[layer_assignment[v]].push(v);
    }

    // Initial ordering: sort by node index within each layer
    for layer in &mut layers {
        layer.sort_unstable();
    }

    // Scratch buffers reused across all crossing-count calls (hot path)
    let mut crossing_scratch = CrossingScratch::new();

    let mut best_crossings = count_crossings_with(&layers, adj, &mut crossing_scratch);
    // Lazy clone: only allocate best_layers when we find an improvement
    let mut best_layers: Option<Vec<Vec<usize>>> = None;

    // Scratch buffers reused across all barycenter_sort calls
    let mut scratch_pos: Vec<usize> = Vec::new();
    let mut scratch_member: Vec<bool> = Vec::new();
    let mut scratch_bary: Vec<(usize, f64)> = Vec::new();

    for iter in 0..max_iterations {
        if *budget == 0 {
            break;
        }
        *budget = budget.saturating_sub(1);

        if iter % 2 == 0 {
            // Forward sweep
            for i in 1..num_layers {
                barycenter_sort(
                    &mut layers,
                    i,
                    adj,
                    radj,
                    true,
                    budget,
                    &mut scratch_pos,
                    &mut scratch_member,
                    &mut scratch_bary,
                );
            }
        } else {
            // Backward sweep
            for i in (0..num_layers.saturating_sub(1)).rev() {
                barycenter_sort(
                    &mut layers,
                    i,
                    adj,
                    radj,
                    false,
                    budget,
                    &mut scratch_pos,
                    &mut scratch_member,
                    &mut scratch_bary,
                );
            }
        }

        let c = count_crossings_with(&layers, adj, &mut crossing_scratch);
        if c < best_crossings {
            best_crossings = c;
            best_layers = Some(layers.clone());
        }

        if best_crossings == 0 {
            break;
        }

        // Sifting refinement: try repositioning individual nodes for further
        // crossing reduction. Only run on layers with 3+ nodes and when budget
        // permits. Sifting is more expensive than barycenter but finds better
        // solutions for dense graphs.
        if *budget > 0 && c > 0 {
            let mut sift_improved = false;
            for li in 0..num_layers {
                if *budget == 0 {
                    break;
                }
                if layers[li].len() >= 3
                    && sifting_sort(&mut layers, li, adj, budget, &mut crossing_scratch)
                {
                    sift_improved = true;
                }
            }
            if sift_improved {
                let c2 = count_crossings_with(&layers, adj, &mut crossing_scratch);
                if c2 < best_crossings {
                    best_crossings = c2;
                    best_layers = Some(layers.clone());
                }
                if best_crossings == 0 {
                    break;
                }
            }
        }
    }

    match best_layers {
        Some(bl) => bl,
        None => {
            // No sweep improved on the initial ordering — restore it.
            // The initial ordering is sort_unstable() by node index,
            // and sweeps only reorder within layers, so re-sorting recovers it.
            for layer in &mut layers {
                layer.sort_unstable();
            }
            layers
        }
    }
}

#[allow(clippy::too_many_arguments)]
fn barycenter_sort(
    layers: &mut [Vec<usize>],
    layer_idx: usize,
    adj: &[Vec<usize>],
    radj: &[Vec<usize>],
    forward: bool,
    budget: &mut usize,
    scratch_pos: &mut Vec<usize>,
    scratch_member: &mut Vec<bool>,
    scratch_bary: &mut Vec<(usize, f64)>,
) {
    if layers.is_empty() || layer_idx >= layers.len() {
        return;
    }

    let ref_layer_idx = if forward {
        layer_idx.checked_sub(1)
    } else if layer_idx + 1 < layers.len() {
        Some(layer_idx + 1)
    } else {
        None
    };

    let ref_layer_idx = match ref_layer_idx {
        Some(i) => i,
        None => return,
    };

    // Build position map for reference layer using scratch buffers
    let ref_layer = &layers[ref_layer_idx];
    let max_ref = ref_layer.iter().copied().max().unwrap_or(0) + 1;

    scratch_pos.clear();
    scratch_pos.resize(max_ref, 0);
    scratch_member.clear();
    scratch_member.resize(max_ref, false);

    for (p, &v) in ref_layer.iter().enumerate() {
        if v < max_ref {
            scratch_pos[v] = p;
            scratch_member[v] = true;
        }
    }

    // Compute barycenters for nodes in current layer
    let layer = &layers[layer_idx];
    scratch_bary.clear();

    for &v in layer {
        *budget = budget.saturating_sub(1);
        let neighbors: &[usize] = if forward { &radj[v] } else { &adj[v] };

        // Compute sum and count inline to avoid allocating a `relevant` Vec
        let mut sum = 0.0f64;
        let mut count = 0usize;
        for &u in neighbors {
            if u < max_ref && scratch_member[u] {
                sum += scratch_pos[u] as f64;
                count += 1;
            }
        }

        if count == 0 {
            scratch_bary.push((v, f64::MAX));
        } else {
            scratch_bary.push((v, sum / count as f64));
        }
    }

    // Sort by barycenter, tiebreak by node index
    scratch_bary.sort_by(|a, b| a.1.total_cmp(&b.1).then_with(|| a.0.cmp(&b.0)));

    layers[layer_idx] = scratch_bary.iter().map(|(v, _)| *v).collect();
}

/// Sifting refinement pass for crossing minimization.
///
/// For each node in the target layer, removes it and tries reinserting it at
/// every possible position, picking the position with the fewest crossings
/// involving this layer's edges. This is O(n^2 * E_local) per layer but
/// finds better solutions than barycenter alone for dense graphs.
///
/// Returns `true` if any improvement was made.
fn sifting_sort(
    layers: &mut [Vec<usize>],
    layer_idx: usize,
    adj: &[Vec<usize>],
    budget: &mut usize,
    scratch: &mut CrossingScratch,
) -> bool {
    let layer_len = layers[layer_idx].len();
    if layer_len <= 2 {
        return false; // No benefit for layers with 0-2 nodes
    }

    let mut improved = false;
    // Process nodes in the order they appear in the layer
    let node_order: Vec<usize> = layers[layer_idx].clone();

    for node in node_order {
        if *budget == 0 {
            break;
        }
        // Budget: each sift costs proportional to layer size
        *budget = budget.saturating_sub(1);

        // Find and remove the node from its current position
        let cur_pos = match layers[layer_idx].iter().position(|&v| v == node) {
            Some(p) => p,
            None => continue,
        };
        layers[layer_idx].remove(cur_pos);

        // Baseline: crossings at the layer with the node removed (re-inserted at cur_pos)
        layers[layer_idx].insert(cur_pos, node);
        let baseline = count_crossings_at_with(layers, layer_idx, adj, scratch);
        layers[layer_idx].remove(cur_pos);

        // Try every position and find the one with minimum crossings
        let len_without = layers[layer_idx].len();
        let mut best_pos = cur_pos;
        let mut best_crossings = baseline;

        for pos in 0..=len_without {
            if pos == cur_pos {
                continue; // Already measured as baseline
            }
            layers[layer_idx].insert(pos, node);
            let c = count_crossings_at_with(layers, layer_idx, adj, scratch);
            layers[layer_idx].remove(pos);
            if c < best_crossings {
                best_crossings = c;
                best_pos = pos;
            }
        }

        // Reinsert at the best position
        layers[layer_idx].insert(best_pos, node);
        if best_pos != cur_pos {
            improved = true;
        }
    }

    improved
}

// ---------------------------------------------------------------------------
// Phase 4: Coordinate assignment — centering + median refinement
// ---------------------------------------------------------------------------

fn assign_coordinates(
    layers: &[Vec<usize>],
    graph: &LayoutGraph,
    config: &LayoutConfig,
    budget: &mut usize,
) -> (Vec<f64>, Vec<f64>) {
    let n = graph.num_nodes;
    let mut x = vec![0.0f64; n];
    let mut y = vec![0.0f64; n];

    // Place nodes in each layer
    for (layer_idx, layer) in layers.iter().enumerate() {
        let layer_y = layer_idx as f64 * (config.node_height + config.layer_spacing);
        let total_width: f64 = layer.iter().map(|&v| graph.node_widths[v]).sum::<f64>()
            + (layer.len().saturating_sub(1)) as f64 * config.node_spacing;
        let mut cx = -total_width / 2.0;

        for &v in layer {
            let w = graph.node_widths[v];
            x[v] = cx + w / 2.0;
            y[v] = layer_y;
            cx += w + config.node_spacing;
        }
    }

    // Median refinement passes — reuse buffers across iterations
    let passes = 4.min(config.max_crossing_iterations);
    let mut neighbor_buf: Vec<f64> = Vec::new();
    let mut sorted_layer_buf: Vec<usize> = Vec::new();
    for _ in 0..passes {
        if *budget == 0 {
            break;
        }
        *budget = budget.saturating_sub(1);

        for layer in layers.iter() {
            for &v in layer {
                neighbor_buf.clear();
                neighbor_buf.extend(
                    graph.adj[v]
                        .iter()
                        .chain(graph.radj[v].iter())
                        .map(|&u| x[u]),
                );
                if !neighbor_buf.is_empty() {
                    neighbor_buf.sort_by(|a, b| a.total_cmp(b));
                    let median = neighbor_buf[neighbor_buf.len() / 2];
                    x[v] = (x[v] + median) / 2.0;
                }
            }
        }

        // Resolve overlaps within layers
        for layer in layers.iter() {
            sorted_layer_buf.clear();
            sorted_layer_buf.extend_from_slice(layer);
            sorted_layer_buf.sort_by(|&a, &b| x[a].total_cmp(&x[b]).then_with(|| a.cmp(&b)));

            for i in 1..sorted_layer_buf.len() {
                let prev = sorted_layer_buf[i - 1];
                let curr = sorted_layer_buf[i];
                let min_gap =
                    (graph.node_widths[prev] + graph.node_widths[curr]) / 2.0 + config.node_spacing;
                if x[curr] - x[prev] < min_gap {
                    x[curr] = x[prev] + min_gap;
                }
            }
        }
    }

    (x, y)
}

fn remap_for_direction(x: &mut [f64], y: &mut [f64], direction: GraphDirection) {
    match direction {
        GraphDirection::TB | GraphDirection::TD => {}
        GraphDirection::BT => {
            let max_y = y.iter().copied().fold(f64::NEG_INFINITY, f64::max);
            for yi in y.iter_mut() {
                *yi = max_y - *yi;
            }
        }
        GraphDirection::LR => {
            for i in 0..x.len() {
                std::mem::swap(&mut x[i], &mut y[i]);
            }
        }
        GraphDirection::RL => {
            let max_y = y.iter().copied().fold(f64::NEG_INFINITY, f64::max);
            for i in 0..x.len() {
                std::mem::swap(&mut x[i], &mut y[i]);
                x[i] = max_y - x[i];
            }
        }
    }
}

// ---------------------------------------------------------------------------
// Post-processing: cluster boxes
// ---------------------------------------------------------------------------

fn compute_cluster_boxes(
    graph: &LayoutGraph,
    x: &[f64],
    y: &[f64],
    display_widths: &[f64],
    display_heights: &[f64],
    config: &LayoutConfig,
) -> Vec<ClusterBox> {
    if config.collapse_clusters {
        return Vec::new();
    }

    graph
        .cluster_members
        .iter()
        .filter_map(|(cluster_id, members)| {
            if members.is_empty() {
                return None;
            }

            let mut min_x = f64::INFINITY;
            let mut max_x = f64::NEG_INFINITY;
            let mut min_y = f64::INFINITY;
            let mut max_y = f64::NEG_INFINITY;

            for &v in members {
                let hw = display_widths[v] / 2.0;
                let hh = display_heights[v] / 2.0;
                min_x = min_x.min(x[v] - hw);
                max_x = max_x.max(x[v] + hw);
                min_y = min_y.min(y[v] - hh);
                max_y = max_y.max(y[v] + hh);
            }

            let pad = config.cluster_padding;
            Some(ClusterBox {
                ir_cluster: *cluster_id,
                x: min_x - pad,
                y: min_y - pad,
                width: (max_x - min_x) + 2.0 * pad,
                height: (max_y - min_y) + 2.0 * pad,
                padding: pad,
            })
        })
        .collect()
}

// ---------------------------------------------------------------------------
// Post-processing: port resolution
// ---------------------------------------------------------------------------

fn compute_ports(
    ir: &MermaidDiagramIr,
    x: &[f64],
    y: &[f64],
    node_widths: &[f64],
    node_heights: &[f64],
    direction: GraphDirection,
) -> Vec<PortPoint> {
    let num_nodes = x.len();
    ir.ports
        .iter()
        .enumerate()
        .filter_map(|(i, port)| {
            let nid = port.node.0;
            if nid >= num_nodes {
                return None;
            }
            let (px, py, side) = match port.side_hint {
                IrPortSideHint::Horizontal => match direction {
                    GraphDirection::LR => {
                        (x[nid] + node_widths[nid] / 2.0, y[nid], PortSide::Right)
                    }
                    GraphDirection::RL => (x[nid] - node_widths[nid] / 2.0, y[nid], PortSide::Left),
                    _ => (x[nid] + node_widths[nid] / 2.0, y[nid], PortSide::Right),
                },
                IrPortSideHint::Vertical => match direction {
                    GraphDirection::BT => (x[nid], y[nid] - node_heights[nid] / 2.0, PortSide::Top),
                    _ => (x[nid], y[nid] + node_heights[nid] / 2.0, PortSide::Bottom),
                },
                IrPortSideHint::Auto => match direction {
                    GraphDirection::LR => {
                        (x[nid] + node_widths[nid] / 2.0, y[nid], PortSide::Right)
                    }
                    GraphDirection::RL => (x[nid] - node_widths[nid] / 2.0, y[nid], PortSide::Left),
                    GraphDirection::BT => (x[nid], y[nid] - node_heights[nid] / 2.0, PortSide::Top),
                    _ => (x[nid], y[nid] + node_heights[nid] / 2.0, PortSide::Bottom),
                },
            };

            Some(PortPoint {
                ir_port: IrPortId(i),
                ir_node: port.node,
                x: px,
                y: py,
                side,
            })
        })
        .collect()
}

// ---------------------------------------------------------------------------
// Post-processing: edge routing (straight-line boundary-to-boundary)
// ---------------------------------------------------------------------------

fn route_edges_simple(
    ir: &MermaidDiagramIr,
    x: &[f64],
    y: &[f64],
    node_widths: &[f64],
    node_heights: &[f64],
    reversed_edges: &[(usize, usize)],
) -> (Vec<RoutedEdge>, RouteGrid) {
    let reversed_set: std::collections::HashSet<(usize, usize)> =
        reversed_edges.iter().copied().collect();

    let mut edges = Vec::new();
    let mut v_channels: Vec<f64> = Vec::new();
    let mut h_channels: Vec<f64> = Vec::new();

    let num_nodes = x.len();
    for (idx, edge) in ir.edges.iter().enumerate() {
        let Some(from_id) = resolve_node(ir, edge.from, num_nodes) else {
            continue;
        };
        let Some(to_id) = resolve_node(ir, edge.to, num_nodes) else {
            continue;
        };
        let is_reversed = reversed_set.contains(&(from_id, to_id));

        // Always clip from→to in the original IR direction so waypoints
        // match the `from`/`to` fields consumers will use for rendering.
        let (sx, sy) = clip_to_boundary(
            x[from_id],
            y[from_id],
            node_widths[from_id],
            node_heights[from_id],
            x[to_id],
            y[to_id],
        );
        let (dx, dy) = clip_to_boundary(
            x[to_id],
            y[to_id],
            node_widths[to_id],
            node_heights[to_id],
            x[from_id],
            y[from_id],
        );

        v_channels.push((sx + dx) / 2.0);
        h_channels.push((sy + dy) / 2.0);

        edges.push(RoutedEdge {
            ir_edge_idx: idx,
            from: IrNodeId(from_id),
            to: IrNodeId(to_id),
            waypoints: vec![(sx, sy), (dx, dy)],
            reversed: is_reversed,
        });
    }

    v_channels.sort_by(|a, b| a.total_cmp(b));
    v_channels.dedup();
    h_channels.sort_by(|a, b| a.total_cmp(b));
    h_channels.dedup();

    let grid = RouteGrid {
        vertical_channels: v_channels,
        horizontal_channels: h_channels,
    };

    (edges, grid)
}

fn clip_to_boundary(cx: f64, cy: f64, w: f64, h: f64, target_x: f64, target_y: f64) -> (f64, f64) {
    let dx = target_x - cx;
    let dy = target_y - cy;

    if dx.abs() < 1e-12 && dy.abs() < 1e-12 {
        return (cx, cy);
    }

    let hw = w / 2.0;
    let hh = h / 2.0;

    // Scale factor to hit the rectangle boundary
    let sx = if dx.abs() > 1e-12 {
        hw / dx.abs()
    } else {
        f64::INFINITY
    };
    let sy = if dy.abs() > 1e-12 {
        hh / dy.abs()
    } else {
        f64::INFINITY
    };
    let s = sx.min(sy);

    (cx + dx * s, cy + dy * s)
}

// ---------------------------------------------------------------------------
// Quality scoring
// ---------------------------------------------------------------------------

impl LayoutQuality {
    fn compute_from(
        layers: &[Vec<usize>],
        adj: &[Vec<usize>],
        edges: &[RoutedEdge],
        x: &[f64],
    ) -> Self {
        let crossings = count_crossings(layers, adj);

        let bends: usize = edges
            .iter()
            .map(|e| e.waypoints.len().saturating_sub(2))
            .sum();

        // Single pass: compute mean once per layer, use for both variance and asymmetry
        let mut variance = 0.0;
        let mut layer_count = 0;
        let mut asymmetry = 0.0;
        let mut asym_count = 0;
        for layer in layers {
            if layer.is_empty() {
                continue;
            }
            let mean: f64 = layer.iter().map(|&v| x[v]).sum::<f64>() / layer.len() as f64;

            // Asymmetry: mean absolute deviation from center
            for &v in layer {
                asymmetry += (x[v] - mean).abs();
                asym_count += 1;
            }

            // Variance (only for layers with >1 node)
            if layer.len() > 1 {
                let var: f64 = layer
                    .iter()
                    .map(|&v| (x[v] - mean) * (x[v] - mean))
                    .sum::<f64>()
                    / layer.len() as f64;
                variance += var;
                layer_count += 1;
            }
        }
        if layer_count > 0 {
            variance /= layer_count as f64;
        }
        if asym_count > 0 {
            asymmetry /= asym_count as f64;
        }

        let total_score =
            crossings as f64 * 10.0 + bends as f64 * 2.0 + variance * 0.1 + asymmetry * 0.5;

        Self {
            crossings,
            bends,
            variance,
            asymmetry,
            total_score,
        }
    }
}

// ---------------------------------------------------------------------------
// Bounds computation
// ---------------------------------------------------------------------------

fn compute_bounds(nodes: &[NodeBox]) -> (f64, f64, f64, f64) {
    if nodes.is_empty() {
        return (0.0, 0.0, 0.0, 0.0);
    }

    let mut min_x = f64::INFINITY;
    let mut max_x = f64::NEG_INFINITY;
    let mut min_y = f64::INFINITY;
    let mut max_y = f64::NEG_INFINITY;

    for n in nodes {
        min_x = min_x.min(n.left());
        max_x = max_x.max(n.right());
        min_y = min_y.min(n.top());
        max_y = max_y.max(n.bottom());
    }

    (min_x, min_y, max_x, max_y)
}

// ---------------------------------------------------------------------------
// Public API
// ---------------------------------------------------------------------------

/// Layout a diagram using default configuration.
#[must_use]
pub fn layout_diagram(ir: &MermaidDiagramIr) -> DiagramLayout {
    let config = LayoutConfig::from_ir(ir);
    layout_diagram_with_config(ir, &config)
}

/// Layout a diagram with explicit configuration.
#[must_use]
pub fn layout_diagram_with_config(ir: &MermaidDiagramIr, config: &LayoutConfig) -> DiagramLayout {
    if ir.nodes.is_empty() {
        return DiagramLayout {
            nodes: Vec::new(),
            clusters: Vec::new(),
            ports: Vec::new(),
            edges: Vec::new(),
            route_grid: RouteGrid::default(),
            bounds: (0.0, 0.0, 0.0, 0.0),
            quality: LayoutQuality {
                crossings: 0,
                bends: 0,
                variance: 0.0,
                asymmetry: 0.0,
                total_score: 0.0,
            },
            degraded: false,
        };
    }

    let mut budget = config.iteration_budget;
    let mut graph = LayoutGraph::from_ir(ir, config);

    // Phase 1: Cycle removal
    let cycle_info = remove_cycles(&mut graph, &mut budget);

    // Phase 2: Layer assignment
    let layer_assignment = assign_layers(&graph, &mut budget);

    // Phase 3: Crossing minimization
    let layers = minimize_crossings(
        &layer_assignment,
        &graph.adj,
        &graph.radj,
        graph.num_nodes,
        config.max_crossing_iterations,
        &mut budget,
    );

    // Phase 4: Coordinate assignment
    let (mut x, mut y) = assign_coordinates(&layers, &graph, config, &mut budget);

    // Direction remapping
    remap_for_direction(&mut x, &mut y, ir.direction);

    // Compute display dimensions (swapped for LR/RL since axes are swapped)
    let (display_widths, display_heights) = match ir.direction {
        GraphDirection::LR | GraphDirection::RL => {
            (graph.node_heights.clone(), graph.node_widths.clone())
        }
        _ => (graph.node_widths.clone(), graph.node_heights.clone()),
    };

    // Build node boxes
    let nodes: Vec<NodeBox> = (0..graph.num_nodes)
        .map(|v| NodeBox {
            ir_node: IrNodeId(v),
            cx: x[v],
            cy: y[v],
            width: display_widths[v],
            height: display_heights[v],
        })
        .collect();

    // Post-processing (use display dimensions, not internal TB dimensions)
    let clusters = compute_cluster_boxes(&graph, &x, &y, &display_widths, &display_heights, config);
    let ports = compute_ports(ir, &x, &y, &display_widths, &display_heights, ir.direction);
    let (edges, route_grid) = route_edges_simple(
        ir,
        &x,
        &y,
        &display_widths,
        &display_heights,
        &cycle_info.reversed,
    );
    let quality = LayoutQuality::compute_from(&layers, &graph.adj, &edges, &x);
    let bounds = compute_bounds(&nodes);
    let degraded = budget == 0;

    DiagramLayout {
        nodes,
        clusters,
        ports,
        edges,
        route_grid,
        bounds,
        quality,
        degraded,
    }
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

#[cfg(test)]
mod tests {
    use super::*;
    use crate::mermaid::*;
    use std::collections::BTreeMap;

    // -- Test helper --

    fn dummy_span() -> Span {
        Span {
            start: Position {
                line: 1,
                col: 1,
                byte: 0,
            },
            end: Position {
                line: 1,
                col: 1,
                byte: 0,
            },
        }
    }

    fn make_test_ir(
        node_labels: &[&str],
        edges: &[(usize, usize)],
        direction: GraphDirection,
    ) -> MermaidDiagramIr {
        let nodes: Vec<IrNode> = node_labels
            .iter()
            .map(|label| IrNode {
                id: label.to_string(),
                label: None,
                shape: NodeShape::Rect,
                classes: Vec::new(),
                style_ref: None,
                span_primary: dummy_span(),
                span_all: Vec::new(),
                implicit: false,
                members: Vec::new(),
                annotation: None,
            })
            .collect();

        let ir_edges: Vec<IrEdge> = edges
            .iter()
            .map(|&(from, to)| IrEdge {
                from: IrEndpoint::Node(IrNodeId(from)),
                to: IrEndpoint::Node(IrNodeId(to)),
                arrow: "-->".to_string(),
                label: None,
                style_ref: None,
                span: dummy_span(),
            })
            .collect();

        MermaidDiagramIr {
            diagram_type: DiagramType::Graph,
            direction,
            nodes,
            edges: ir_edges,
            ports: Vec::new(),
            clusters: Vec::new(),
            labels: Vec::new(),
            pie_entries: Vec::new(),
            pie_title: None,
            pie_show_data: false,
            style_refs: Vec::new(),
            links: Vec::new(),
            meta: MermaidDiagramMeta {
                diagram_type: DiagramType::Graph,
                direction,
                support_level: MermaidSupportLevel::Supported,
                init: MermaidInitParse {
                    config: MermaidInitConfig {
                        theme: None,
                        theme_variables: BTreeMap::new(),
                        flowchart_direction: None,
                    },
                    warnings: Vec::new(),
                    errors: Vec::new(),
                },
                theme_overrides: MermaidThemeOverrides {
                    theme: None,
                    theme_variables: BTreeMap::new(),
                },
                guard: MermaidGuardReport::default(),
            },
            constraints: vec![],
            quadrant_points: Vec::new(),
            quadrant_title: None,
            quadrant_x_axis: None,
            quadrant_y_axis: None,
            quadrant_labels: [None, None, None, None],
            packet_fields: Vec::new(),
            packet_title: None,
            packet_bits_per_row: 32,
            sequence_participants: Vec::new(),
            sequence_controls: Vec::new(),
            sequence_notes: Vec::new(),
            sequence_activations: Vec::new(),
            sequence_autonumber: false,
            gantt_title: None,
            gantt_sections: Vec::new(),
            gantt_tasks: Vec::new(),
        }
    }

    fn make_test_ir_with_clusters(
        node_labels: &[&str],
        edges: &[(usize, usize)],
        clusters: &[(usize, &[usize])],
        direction: GraphDirection,
    ) -> MermaidDiagramIr {
        let mut ir = make_test_ir(node_labels, edges, direction);
        ir.clusters = clusters
            .iter()
            .map(|&(id, members)| IrCluster {
                id: IrClusterId(id),
                title: None,
                members: members.iter().map(|&m| IrNodeId(m)).collect(),
                span: dummy_span(),
            })
            .collect();
        ir
    }

    // -- Primitive tests --

    #[test]
    fn node_box_accessors() {
        let nb = NodeBox {
            ir_node: IrNodeId(0),
            cx: 100.0,
            cy: 50.0,
            width: 80.0,
            height: 40.0,
        };
        assert!((nb.left() - 60.0).abs() < 1e-9);
        assert!((nb.right() - 140.0).abs() < 1e-9);
        assert!((nb.top() - 30.0).abs() < 1e-9);
        assert!((nb.bottom() - 70.0).abs() < 1e-9);
    }

    #[test]
    fn layout_padding_default() {
        let config = LayoutConfig::default();
        assert!((config.cluster_padding - 10.0).abs() < 1e-9);
        assert!((config.node_spacing - 30.0).abs() < 1e-9);
    }

    #[test]
    fn config_from_ir_respects_degradation() {
        let mut ir = make_test_ir(&["A"], &[], GraphDirection::TB);
        ir.meta.guard.layout_budget_exceeded = true;
        ir.meta.guard.degradation.collapse_clusters = true;
        let config = LayoutConfig::from_ir(&ir);
        assert_eq!(config.max_crossing_iterations, 4);
        assert!(config.collapse_clusters);
    }

    // -- Cycle removal tests --

    #[test]
    fn cycle_removal_acyclic_unchanged() {
        let ir = make_test_ir(&["A", "B", "C"], &[(0, 1), (1, 2)], GraphDirection::TB);
        let config = LayoutConfig::default();
        let mut graph = LayoutGraph::from_ir(&ir, &config);
        let mut budget = 10_000;
        let info = remove_cycles(&mut graph, &mut budget);
        assert!(info.reversed.is_empty());
    }

    #[test]
    fn cycle_removal_simple_cycle() {
        let ir = make_test_ir(
            &["A", "B", "C"],
            &[(0, 1), (1, 2), (2, 0)],
            GraphDirection::TB,
        );
        let config = LayoutConfig::default();
        let mut graph = LayoutGraph::from_ir(&ir, &config);
        let mut budget = 10_000;
        let info = remove_cycles(&mut graph, &mut budget);
        assert!(!info.reversed.is_empty());
    }

    #[test]
    fn cycle_removal_self_loop() {
        let ir = make_test_ir(&["A", "B"], &[(0, 0), (0, 1)], GraphDirection::TB);
        let config = LayoutConfig::default();
        let mut graph = LayoutGraph::from_ir(&ir, &config);
        let mut budget = 10_000;
        let _info = remove_cycles(&mut graph, &mut budget);
        // Self-loops removed; layout still works
        let layers = assign_layers(&graph, &mut budget);
        assert_eq!(layers.len(), 2);
    }

    #[test]
    fn cycle_removal_multi_cycle() {
        let ir = make_test_ir(
            &["A", "B", "C", "D"],
            &[(0, 1), (1, 2), (2, 0), (2, 3)],
            GraphDirection::TB,
        );
        let config = LayoutConfig::default();
        let mut graph = LayoutGraph::from_ir(&ir, &config);
        let mut budget = 10_000;
        let info = remove_cycles(&mut graph, &mut budget);
        assert!(!info.reversed.is_empty());
    }

    #[test]
    fn cycle_removal_deterministic() {
        let ir = make_test_ir(
            &["A", "B", "C"],
            &[(0, 1), (1, 2), (2, 0)],
            GraphDirection::TB,
        );
        let config = LayoutConfig::default();

        let mut g1 = LayoutGraph::from_ir(&ir, &config);
        let mut b1 = 10_000;
        let r1 = remove_cycles(&mut g1, &mut b1);

        let mut g2 = LayoutGraph::from_ir(&ir, &config);
        let mut b2 = 10_000;
        let r2 = remove_cycles(&mut g2, &mut b2);

        assert_eq!(r1.reversed.len(), r2.reversed.len());
    }

    #[test]
    fn cycle_removal_budget_exhaustion_still_orders_all_nodes() {
        let ir = make_test_ir(
            &["A", "B", "C", "D"],
            &[(0, 1), (1, 2), (2, 0), (2, 3)],
            GraphDirection::TB,
        );
        let config = LayoutConfig::default();
        let mut graph = LayoutGraph::from_ir(&ir, &config);
        let mut budget = 0;
        let _info = remove_cycles(&mut graph, &mut budget);

        let mut layer_budget = 10_000;
        let layers = assign_layers(&graph, &mut layer_budget);
        assert_eq!(layers.len(), ir.nodes.len());
        let max_layer = layers.iter().copied().max().unwrap_or(0);
        assert!(max_layer <= ir.nodes.len().saturating_sub(1));
    }

    // -- Layering tests --

    #[test]
    fn layering_linear_chain() {
        let ir = make_test_ir(
            &["A", "B", "C", "D"],
            &[(0, 1), (1, 2), (2, 3)],
            GraphDirection::TB,
        );
        let config = LayoutConfig::default();
        let graph = LayoutGraph::from_ir(&ir, &config);
        let mut budget = 10_000;
        let layers = assign_layers(&graph, &mut budget);
        assert_eq!(layers, vec![0, 1, 2, 3]);
    }

    #[test]
    fn layering_diamond() {
        // A -> B, A -> C, B -> D, C -> D
        let ir = make_test_ir(
            &["A", "B", "C", "D"],
            &[(0, 1), (0, 2), (1, 3), (2, 3)],
            GraphDirection::TB,
        );
        let config = LayoutConfig::default();
        let graph = LayoutGraph::from_ir(&ir, &config);
        let mut budget = 10_000;
        let layers = assign_layers(&graph, &mut budget);
        assert_eq!(layers[0], 0); // A at top
        assert_eq!(layers[1], 1); // B
        assert_eq!(layers[2], 1); // C same layer as B
        assert_eq!(layers[3], 2); // D at bottom
    }

    #[test]
    fn layering_single_node() {
        let ir = make_test_ir(&["A"], &[], GraphDirection::TB);
        let config = LayoutConfig::default();
        let graph = LayoutGraph::from_ir(&ir, &config);
        let mut budget = 10_000;
        let layers = assign_layers(&graph, &mut budget);
        assert_eq!(layers, vec![0]);
    }

    #[test]
    fn layering_disconnected() {
        let ir = make_test_ir(&["A", "B", "C"], &[], GraphDirection::TB);
        let config = LayoutConfig::default();
        let graph = LayoutGraph::from_ir(&ir, &config);
        let mut budget = 10_000;
        let layers = assign_layers(&graph, &mut budget);
        // All disconnected nodes on layer 0
        assert_eq!(layers, vec![0, 0, 0]);
    }

    // -- Crossing minimization tests --

    #[test]
    fn crossings_no_crossing_stable() {
        // A -> C, B -> D — no crossing possible
        let ir = make_test_ir(&["A", "B", "C", "D"], &[(0, 2), (1, 3)], GraphDirection::TB);
        let config = LayoutConfig::default();
        let graph = LayoutGraph::from_ir(&ir, &config);
        let mut budget = 10_000;
        let layer_assignment = assign_layers(&graph, &mut budget);
        let layers = minimize_crossings(
            &layer_assignment,
            &graph.adj,
            &graph.radj,
            graph.num_nodes,
            config.max_crossing_iterations,
            &mut budget,
        );
        let c = count_crossings(&layers, &graph.adj);
        assert_eq!(c, 0);
    }

    #[test]
    fn crossings_swap_reduces() {
        // A -> D, B -> C — initial ordering has crossing, barycenter should fix
        let ir = make_test_ir(&["A", "B", "C", "D"], &[(0, 3), (1, 2)], GraphDirection::TB);
        let config = LayoutConfig::default();
        let graph = LayoutGraph::from_ir(&ir, &config);
        let mut budget = 10_000;
        let layer_assignment = assign_layers(&graph, &mut budget);
        let layers = minimize_crossings(
            &layer_assignment,
            &graph.adj,
            &graph.radj,
            graph.num_nodes,
            config.max_crossing_iterations,
            &mut budget,
        );
        let c = count_crossings(&layers, &graph.adj);
        assert_eq!(c, 0);
    }

    #[test]
    fn crossings_bounded_iterations() {
        let ir = make_test_ir(&["A", "B", "C", "D"], &[(0, 3), (1, 2)], GraphDirection::TB);
        let config = LayoutConfig {
            max_crossing_iterations: 1,
            ..LayoutConfig::default()
        };
        let graph = LayoutGraph::from_ir(&ir, &config);
        let mut budget = 10_000;
        let layer_assignment = assign_layers(&graph, &mut budget);
        let layers = minimize_crossings(
            &layer_assignment,
            &graph.adj,
            &graph.radj,
            graph.num_nodes,
            config.max_crossing_iterations,
            &mut budget,
        );
        // Should still produce valid layers
        assert!(!layers.is_empty());
    }

    #[test]
    fn crossings_deterministic() {
        let ir = make_test_ir(
            &["A", "B", "C", "D", "E"],
            &[(0, 3), (1, 4), (2, 3), (0, 4)],
            GraphDirection::TB,
        );
        let config = LayoutConfig::default();

        let result1 = layout_diagram_with_config(&ir, &config);
        let result2 = layout_diagram_with_config(&ir, &config);

        for (n1, n2) in result1.nodes.iter().zip(result2.nodes.iter()) {
            assert!((n1.cx - n2.cx).abs() < 1e-12);
            assert!((n1.cy - n2.cy).abs() < 1e-12);
        }
    }

    // -- Coordinate tests --

    #[test]
    fn coordinates_single_layer_centered() {
        let ir = make_test_ir(&["A", "B", "C"], &[], GraphDirection::TB);
        let config = LayoutConfig::default();
        let layout = layout_diagram_with_config(&ir, &config);
        // Center of mass should be near zero
        let mean_x: f64 =
            layout.nodes.iter().map(|n| n.cx).sum::<f64>() / layout.nodes.len() as f64;
        assert!(mean_x.abs() < config.node_width);
    }

    #[test]
    fn coordinates_two_layers_no_overlap() {
        let ir = make_test_ir(&["A", "B", "C", "D"], &[(0, 2), (1, 3)], GraphDirection::TB);
        let config = LayoutConfig::default();
        let layout = layout_diagram_with_config(&ir, &config);

        // No overlaps
        for i in 0..layout.nodes.len() {
            for j in (i + 1)..layout.nodes.len() {
                assert!(
                    !layout.nodes[i].overlaps(&layout.nodes[j]),
                    "Nodes {} and {} overlap",
                    i,
                    j
                );
            }
        }
    }

    #[test]
    fn coordinates_direction_tb() {
        let ir = make_test_ir(&["A", "B"], &[(0, 1)], GraphDirection::TB);
        let layout = layout_diagram(&ir);
        // In TB mode, A should be above B (smaller y)
        assert!(layout.nodes[0].cy < layout.nodes[1].cy);
    }

    #[test]
    fn coordinates_direction_bt() {
        let ir = make_test_ir(&["A", "B"], &[(0, 1)], GraphDirection::BT);
        let layout = layout_diagram(&ir);
        // In BT mode, A should be below B (larger y)
        assert!(layout.nodes[0].cy > layout.nodes[1].cy);
    }

    #[test]
    fn coordinates_direction_lr() {
        let ir = make_test_ir(&["A", "B"], &[(0, 1)], GraphDirection::LR);
        let layout = layout_diagram(&ir);
        // In LR mode, A should be left of B (smaller x)
        assert!(layout.nodes[0].cx < layout.nodes[1].cx);
    }

    #[test]
    fn coordinates_direction_rl() {
        let ir = make_test_ir(&["A", "B"], &[(0, 1)], GraphDirection::RL);
        let layout = layout_diagram(&ir);
        // In RL mode, A should be right of B (larger x)
        assert!(layout.nodes[0].cx > layout.nodes[1].cx);
    }

    #[test]
    fn coordinates_direction_td() {
        let ir = make_test_ir(&["A", "B"], &[(0, 1)], GraphDirection::TD);
        let layout = layout_diagram(&ir);
        // TD is alias for TB
        assert!(layout.nodes[0].cy < layout.nodes[1].cy);
    }

    // -- Cluster tests --

    #[test]
    fn cluster_encloses_members() {
        let ir = make_test_ir_with_clusters(
            &["A", "B", "C"],
            &[(0, 1), (1, 2)],
            &[(0, &[0, 1])],
            GraphDirection::TB,
        );
        let layout = layout_diagram(&ir);
        assert_eq!(layout.clusters.len(), 1);
        let cluster = &layout.clusters[0];

        // Cluster should enclose nodes 0 and 1
        for &idx in &[0usize, 1] {
            let node = &layout.nodes[idx];
            assert!(
                node.left() >= cluster.x,
                "Node {} left outside cluster",
                idx
            );
            assert!(
                node.right() <= cluster.x + cluster.width,
                "Node {} right outside cluster",
                idx
            );
            assert!(node.top() >= cluster.y, "Node {} top outside cluster", idx);
            assert!(
                node.bottom() <= cluster.y + cluster.height,
                "Node {} bottom outside cluster",
                idx
            );
        }
    }

    #[test]
    fn cluster_padding_applied() {
        let ir =
            make_test_ir_with_clusters(&["A", "B"], &[(0, 1)], &[(0, &[0, 1])], GraphDirection::TB);
        let config = LayoutConfig {
            cluster_padding: 20.0,
            ..LayoutConfig::default()
        };
        let layout = layout_diagram_with_config(&ir, &config);
        assert_eq!(layout.clusters.len(), 1);
        assert!((layout.clusters[0].padding - 20.0).abs() < 1e-9);
    }

    #[test]
    fn cluster_collapsed_empty() {
        let ir =
            make_test_ir_with_clusters(&["A", "B"], &[(0, 1)], &[(0, &[0, 1])], GraphDirection::TB);
        let config = LayoutConfig {
            collapse_clusters: true,
            ..LayoutConfig::default()
        };
        let layout = layout_diagram_with_config(&ir, &config);
        assert!(layout.clusters.is_empty());
    }

    // -- No-overlap invariant --

    #[test]
    fn no_overlap_invariant() {
        let ir = make_test_ir(
            &["A", "B", "C", "D", "E"],
            &[(0, 1), (0, 2), (1, 3), (2, 4), (3, 4)],
            GraphDirection::TB,
        );
        let layout = layout_diagram(&ir);
        for i in 0..layout.nodes.len() {
            for j in (i + 1)..layout.nodes.len() {
                assert!(
                    !layout.nodes[i].overlaps(&layout.nodes[j]),
                    "Nodes {} and {} overlap",
                    i,
                    j
                );
            }
        }
    }

    // -- Integration tests --

    #[test]
    fn integration_empty_ir() {
        let ir = make_test_ir(&[], &[], GraphDirection::TB);
        let layout = layout_diagram(&ir);
        assert!(layout.nodes.is_empty());
        assert!(layout.edges.is_empty());
        assert!(!layout.degraded);
    }

    #[test]
    fn integration_single_node() {
        let ir = make_test_ir(&["A"], &[], GraphDirection::TB);
        let layout = layout_diagram(&ir);
        assert_eq!(layout.nodes.len(), 1);
        assert_eq!(layout.edges.len(), 0);
        assert!(!layout.degraded);
    }

    #[test]
    fn integration_linear_chain() {
        let ir = make_test_ir(&["A", "B", "C"], &[(0, 1), (1, 2)], GraphDirection::TB);
        let layout = layout_diagram(&ir);
        assert_eq!(layout.nodes.len(), 3);
        assert_eq!(layout.edges.len(), 2);
        // Nodes should be ordered top-to-bottom
        assert!(layout.nodes[0].cy < layout.nodes[1].cy);
        assert!(layout.nodes[1].cy < layout.nodes[2].cy);
    }

    #[test]
    fn integration_diamond() {
        let ir = make_test_ir(
            &["A", "B", "C", "D"],
            &[(0, 1), (0, 2), (1, 3), (2, 3)],
            GraphDirection::TB,
        );
        let layout = layout_diagram(&ir);
        assert_eq!(layout.nodes.len(), 4);
        assert_eq!(layout.edges.len(), 4);
        // A at top, D at bottom, B and C in middle
        assert!(layout.nodes[0].cy < layout.nodes[1].cy);
        assert!((layout.nodes[1].cy - layout.nodes[2].cy).abs() < 1e-9);
        assert!(layout.nodes[1].cy < layout.nodes[3].cy);
    }

    #[test]
    fn integration_with_cluster() {
        let ir = make_test_ir_with_clusters(
            &["A", "B", "C"],
            &[(0, 1), (1, 2)],
            &[(0, &[0, 1])],
            GraphDirection::TB,
        );
        let layout = layout_diagram(&ir);
        assert_eq!(layout.clusters.len(), 1);
        assert_eq!(layout.nodes.len(), 3);
    }

    #[test]
    fn integration_determinism() {
        let ir = make_test_ir(
            &["A", "B", "C", "D", "E"],
            &[(0, 1), (0, 2), (1, 3), (2, 4), (3, 4)],
            GraphDirection::TB,
        );

        let l1 = layout_diagram(&ir);
        let l2 = layout_diagram(&ir);

        assert_eq!(l1.nodes.len(), l2.nodes.len());
        for (n1, n2) in l1.nodes.iter().zip(l2.nodes.iter()) {
            assert!((n1.cx - n2.cx).abs() < 1e-12);
            assert!((n1.cy - n2.cy).abs() < 1e-12);
            assert!((n1.width - n2.width).abs() < 1e-12);
            assert!((n1.height - n2.height).abs() < 1e-12);
        }
        assert!((l1.quality.total_score - l2.quality.total_score).abs() < 1e-12);
    }

    #[test]
    fn integration_budget_respected() {
        let ir = make_test_ir(
            &["A", "B", "C", "D"],
            &[(0, 1), (1, 2), (2, 3), (3, 0)],
            GraphDirection::TB,
        );
        let config = LayoutConfig {
            iteration_budget: 5,
            max_crossing_iterations: 100,
            ..LayoutConfig::default()
        };
        let layout = layout_diagram_with_config(&ir, &config);
        // Should still produce a valid layout even if degraded
        assert_eq!(layout.nodes.len(), 4);
        // May or may not be degraded depending on how fast budget runs out
    }

    #[test]
    fn edge_routing_produces_waypoints() {
        let ir = make_test_ir(&["A", "B"], &[(0, 1)], GraphDirection::TB);
        let layout = layout_diagram(&ir);
        assert_eq!(layout.edges.len(), 1);
        assert!(layout.edges[0].waypoints.len() >= 2);
    }

    #[test]
    fn quality_score_computed() {
        let ir = make_test_ir(&["A", "B", "C"], &[(0, 1), (1, 2)], GraphDirection::TB);
        let layout = layout_diagram(&ir);
        // Linear chain should have 0 crossings
        assert_eq!(layout.quality.crossings, 0);
        assert!(layout.quality.total_score >= 0.0);
    }

    #[test]
    fn bounds_encompass_all_nodes() {
        let ir = make_test_ir(
            &["A", "B", "C", "D"],
            &[(0, 1), (0, 2), (1, 3), (2, 3)],
            GraphDirection::TB,
        );
        let layout = layout_diagram(&ir);
        let (bx0, by0, bx1, by1) = layout.bounds;
        for n in &layout.nodes {
            assert!(n.left() >= bx0 - 1e-9);
            assert!(n.right() <= bx1 + 1e-9);
            assert!(n.top() >= by0 - 1e-9);
            assert!(n.bottom() <= by1 + 1e-9);
        }
    }

    // -- Golden output determinism --

    fn assert_close(actual: f64, expected: f64, label: &str) {
        assert!(
            (actual - expected).abs() < 1e-9,
            "{label}: expected {expected}, got {actual}"
        );
    }

    #[test]
    fn golden_output_determinism() {
        // Graph 1: 5-node linear chain
        let ir1 = make_test_ir(
            &["A", "B", "C", "D", "E"],
            &[(0, 1), (1, 2), (2, 3), (3, 4)],
            GraphDirection::TB,
        );
        let l1 = layout_diagram(&ir1);
        let expected_cx1 = [0.0, 0.0, 0.0, 0.0, 0.0];
        let expected_cy1 = [0.0, 100.0, 200.0, 300.0, 400.0];
        for (i, n) in l1.nodes.iter().enumerate() {
            assert_close(n.cx, expected_cx1[i], &format!("g1 node[{i}].cx"));
            assert_close(n.cy, expected_cy1[i], &format!("g1 node[{i}].cy"));
        }
        assert_eq!(l1.quality.crossings, 0);
        assert_eq!(l1.quality.bends, 0);
        assert_close(l1.quality.total_score, 0.0, "g1 total_score");

        // Graph 2: Diamond
        let ir2 = make_test_ir(
            &["A", "B", "C", "D"],
            &[(0, 1), (0, 2), (1, 3), (2, 3)],
            GraphDirection::TB,
        );
        let l2 = layout_diagram(&ir2);
        let expected_cx2 = [134.4921875, 97.75390625, 207.75390625, 117.841796875];
        let expected_cy2 = [0.0, 100.0, 100.0, 200.0];
        for (i, n) in l2.nodes.iter().enumerate() {
            assert_close(n.cx, expected_cx2[i], &format!("g2 node[{i}].cx"));
            assert_close(n.cy, expected_cy2[i], &format!("g2 node[{i}].cy"));
        }
        assert_eq!(l2.quality.crossings, 0);
        assert_close(l2.quality.total_score, 316.25, "g2 total_score");

        // Graph 3: Wide graph
        let ir3 = make_test_ir(
            &["A", "B", "C", "D", "E", "F"],
            &[(0, 2), (0, 3), (1, 3), (1, 4), (2, 5), (3, 5), (4, 5)],
            GraphDirection::TB,
        );
        let l3 = layout_diagram(&ir3);
        let expected_cx3 = [
            88.515625,
            198.515625,
            51.9921875,
            161.9921875,
            271.9921875,
            75.41015625,
        ];
        let expected_cy3 = [0.0, 0.0, 100.0, 100.0, 100.0, 200.0];
        for (i, n) in l3.nodes.iter().enumerate() {
            assert_close(n.cx, expected_cx3[i], &format!("g3 node[{i}].cx"));
            assert_close(n.cy, expected_cy3[i], &format!("g3 node[{i}].cy"));
        }
        assert_eq!(l3.quality.crossings, 0);
        assert_close(l3.quality.total_score, 582.0833333333334, "g3 total_score");
    }

    // -- Sifting algorithm tests --

    #[test]
    fn sifting_produces_valid_permutation() {
        // After sifting, the layer should contain the same nodes (just reordered)
        let mut layers = vec![vec![0, 1, 2], vec![3, 4, 5, 6, 7], vec![8, 9]];
        let adj = vec![
            vec![3, 4], // 0 -> 3, 4
            vec![5, 6], // 1 -> 5, 6
            vec![7],    // 2 -> 7
            vec![8],    // 3 -> 8
            vec![9],    // 4 -> 9
            vec![8],    // 5 -> 8
            vec![9],    // 6 -> 9
            vec![8, 9], // 7 -> 8, 9
            vec![],     // 8
            vec![],     // 9
        ];
        let original: Vec<usize> = layers[1].clone();
        let mut budget = 1000;
        sifting_sort(
            &mut layers,
            1,
            &adj,
            &mut budget,
            &mut CrossingScratch::new(),
        );
        let mut sorted_result = layers[1].clone();
        sorted_result.sort_unstable();
        let mut sorted_original = original;
        sorted_original.sort_unstable();
        assert_eq!(
            sorted_result, sorted_original,
            "sifting must be a valid permutation"
        );
    }

    #[test]
    fn sifting_reduces_crossings_on_known_bad_ordering() {
        // Construct a graph where the initial ordering has crossings
        // that sifting should be able to reduce.
        // Layer 0: [0, 1, 2]
        // Layer 1: [3, 4, 5] — intentionally ordered to create crossings
        // Edges: 0->5, 1->3, 2->4 (all crossing if layer 1 is [3,4,5])
        let mut layers = vec![vec![0, 1, 2], vec![3, 4, 5]];
        let adj = vec![
            vec![5], // 0 -> 5
            vec![3], // 1 -> 3
            vec![4], // 2 -> 4
            vec![],  // 3
            vec![],  // 4
            vec![],  // 5
        ];
        let before = count_crossings(&layers, &adj);
        assert!(before > 0, "initial ordering should have crossings");

        let mut budget = 1000;
        sifting_sort(
            &mut layers,
            1,
            &adj,
            &mut budget,
            &mut CrossingScratch::new(),
        );
        let after = count_crossings(&layers, &adj);
        assert!(
            after <= before,
            "sifting should not increase crossings: before={before}, after={after}"
        );
        assert_eq!(
            after, 0,
            "sifting should find the optimal (zero-crossing) ordering"
        );
    }

    #[test]
    fn sifting_respects_budget() {
        // With zero budget, sifting should not modify anything
        let mut layers = vec![vec![0, 1, 2], vec![3, 4, 5]];
        let adj = vec![vec![5], vec![3], vec![4], vec![], vec![], vec![]];
        let original = layers[1].clone();
        let mut budget = 0;
        let improved = sifting_sort(
            &mut layers,
            1,
            &adj,
            &mut budget,
            &mut CrossingScratch::new(),
        );
        assert!(!improved, "sifting with zero budget should not improve");
        assert_eq!(
            layers[1], original,
            "layer should be unchanged with zero budget"
        );
    }

    #[test]
    fn sifting_noop_for_small_layers() {
        // Layers with <= 2 nodes should not be modified
        let mut layers = vec![vec![0], vec![1, 2]];
        let adj = vec![vec![1, 2], vec![], vec![]];
        let mut budget = 1000;
        let improved = sifting_sort(
            &mut layers,
            0,
            &adj,
            &mut budget,
            &mut CrossingScratch::new(),
        );
        assert!(!improved, "single-node layer cannot be improved by sifting");
        let improved2 = sifting_sort(
            &mut layers,
            1,
            &adj,
            &mut budget,
            &mut CrossingScratch::new(),
        );
        assert!(!improved2, "two-node layer should not trigger sifting");
    }

    #[test]
    fn sifting_integrated_in_minimize_crossings() {
        // Verify that the full minimize_crossings pipeline (barycenter + sifting)
        // produces zero crossings on a graph with a known optimal solution.
        // Diamond: A->B, A->C, B->D, C->D (no crossings possible with correct ordering)
        let layer_assignment = vec![0, 1, 1, 2]; // A=0, B=1, C=1, D=2
        let adj = vec![
            vec![1, 2], // A -> B, C
            vec![3],    // B -> D
            vec![3],    // C -> D
            vec![],     // D
        ];
        let radj = vec![
            vec![],     // A
            vec![0],    // B <- A
            vec![0],    // C <- A
            vec![1, 2], // D <- B, C
        ];
        let mut budget = 10_000;
        let result = minimize_crossings(&layer_assignment, &adj, &radj, 4, 10, &mut budget);
        let crossings = count_crossings(&result, &adj);
        assert_eq!(crossings, 0, "diamond graph should have zero crossings");
    }

    #[test]
    fn sifting_improves_dense_graph() {
        // A denser graph where sifting should help beyond barycenter.
        // 3 layers: [0,1,2,3] -> [4,5,6,7] -> [8,9,10,11]
        // With crossing edges that barycenter alone may not fully resolve.
        let layer_assignment = vec![0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2];
        let adj = vec![
            vec![7],  // 0 -> 7
            vec![4],  // 1 -> 4
            vec![6],  // 2 -> 6
            vec![5],  // 3 -> 5
            vec![11], // 4 -> 11
            vec![8],  // 5 -> 8
            vec![10], // 6 -> 10
            vec![9],  // 7 -> 9
            vec![],   // 8
            vec![],   // 9
            vec![],   // 10
            vec![],   // 11
        ];
        let radj = vec![
            vec![],  // 0
            vec![1], // 1 <- 0
            vec![2], // 2 <- 0
            vec![3], // 3 <- 0
            vec![0], // 4 <- 0
            vec![0], // 5 <- 0
            vec![0], // 6 <- 0
            vec![0], // 7 <- 0
            vec![5], // 8 -> 5
            vec![6], // 9 -> 6
            vec![7], // 10 -> 7
            vec![4], // 11 -> 4
        ];
        let mut budget = 50_000;
        let result = minimize_crossings(&layer_assignment, &adj, &radj, 12, 20, &mut budget);
        let crossings = count_crossings(&result, &adj);
        // This graph has an optimal solution with 0 crossings
        assert_eq!(
            crossings, 0,
            "sifting should find zero-crossing ordering for this graph"
        );
    }

    #[test]
    fn count_crossings_pair_matches_full_count() {
        // Verify count_crossings_pair_with gives same result as count_crossings for a 2-layer graph
        let layers = vec![vec![0, 1, 2], vec![3, 4, 5]];
        let adj = vec![vec![5], vec![3], vec![4], vec![], vec![], vec![]];
        let full = count_crossings(&layers, &adj);
        let mut scratch = CrossingScratch::new();
        let pair = count_crossings_pair_with(&layers[0], &layers[1], &adj, &mut scratch);
        assert_eq!(
            full, pair,
            "pair count should match full count for 2-layer graph"
        );
    }

    // =====================================================================
    // Edge-case tests added for bd-1juai
    // =====================================================================

    // -- clip_to_boundary direct tests --

    #[test]
    fn clip_to_boundary_coincident_points() {
        // When target == center, return center
        let (x, y) = clip_to_boundary(10.0, 20.0, 80.0, 40.0, 10.0, 20.0);
        assert!((x - 10.0).abs() < 1e-9);
        assert!((y - 20.0).abs() < 1e-9);
    }

    #[test]
    fn clip_to_boundary_horizontal_target() {
        // Target directly to the right
        let (x, y) = clip_to_boundary(0.0, 0.0, 80.0, 40.0, 100.0, 0.0);
        assert!(
            (x - 40.0).abs() < 1e-9,
            "should clip to right edge: got {x}"
        );
        assert!((y - 0.0).abs() < 1e-9);
    }

    #[test]
    fn clip_to_boundary_vertical_target() {
        // Target directly below
        let (x, y) = clip_to_boundary(0.0, 0.0, 80.0, 40.0, 0.0, 100.0);
        assert!((x - 0.0).abs() < 1e-9);
        assert!(
            (y - 20.0).abs() < 1e-9,
            "should clip to bottom edge: got {y}"
        );
    }

    #[test]
    fn clip_to_boundary_diagonal_target() {
        // Target at 45 degrees from a square node
        let (x, y) = clip_to_boundary(0.0, 0.0, 40.0, 40.0, 100.0, 100.0);
        // For a square with half-width 20, going diagonal: min(20/100, 20/100) = 0.2
        assert!((x - 20.0).abs() < 1e-9, "diagonal x: got {x}");
        assert!((y - 20.0).abs() < 1e-9, "diagonal y: got {y}");
    }

    #[test]
    fn clip_to_boundary_negative_direction() {
        // Target to the left
        let (x, y) = clip_to_boundary(0.0, 0.0, 80.0, 40.0, -100.0, 0.0);
        assert!(
            (x - (-40.0)).abs() < 1e-9,
            "should clip to left edge: got {x}"
        );
        assert!((y - 0.0).abs() < 1e-9);
    }

    // -- compute_bounds direct tests --

    #[test]
    fn compute_bounds_empty() {
        let bounds = compute_bounds(&[]);
        assert_eq!(bounds, (0.0, 0.0, 0.0, 0.0));
    }

    #[test]
    fn compute_bounds_single_node() {
        let nodes = vec![NodeBox {
            ir_node: IrNodeId(0),
            cx: 50.0,
            cy: 30.0,
            width: 20.0,
            height: 10.0,
        }];
        let (x0, y0, x1, y1) = compute_bounds(&nodes);
        assert!((x0 - 40.0).abs() < 1e-9);
        assert!((y0 - 25.0).abs() < 1e-9);
        assert!((x1 - 60.0).abs() < 1e-9);
        assert!((y1 - 35.0).abs() < 1e-9);
    }

    // -- merge_sort_count_inversions direct tests --

    #[test]
    fn merge_sort_inversions_empty() {
        let mut seq: Vec<usize> = vec![];
        let mut buf: Vec<usize> = vec![];
        assert_eq!(merge_sort_count_inversions(&mut seq, &mut buf), 0);
    }

    #[test]
    fn merge_sort_inversions_single() {
        let mut seq = vec![42];
        let mut buf = vec![0];
        assert_eq!(merge_sort_count_inversions(&mut seq, &mut buf), 0);
    }

    #[test]
    fn merge_sort_inversions_sorted() {
        let mut seq = vec![1, 2, 3, 4, 5];
        let mut buf = vec![0; 5];
        assert_eq!(merge_sort_count_inversions(&mut seq, &mut buf), 0);
    }

    #[test]
    fn merge_sort_inversions_reversed() {
        // Fully reversed: n*(n-1)/2 inversions
        let mut seq = vec![5, 4, 3, 2, 1];
        let mut buf = vec![0; 5];
        assert_eq!(merge_sort_count_inversions(&mut seq, &mut buf), 10);
    }

    #[test]
    fn merge_sort_inversions_known() {
        // [3, 1, 2] has inversions (3,1), (3,2) = 2
        let mut seq = vec![3, 1, 2];
        let mut buf = vec![0; 3];
        assert_eq!(merge_sort_count_inversions(&mut seq, &mut buf), 2);
    }

    // -- NodeBox::overlaps edge cases --

    #[test]
    fn node_box_overlaps_touching_not_overlapping() {
        // Boxes that touch at edges should NOT overlap (strict inequality)
        let a = NodeBox {
            ir_node: IrNodeId(0),
            cx: 0.0,
            cy: 0.0,
            width: 10.0,
            height: 10.0,
        };
        let b = NodeBox {
            ir_node: IrNodeId(1),
            cx: 10.0, // b.left() = 5.0 == a.right() = 5.0
            cy: 0.0,
            width: 10.0,
            height: 10.0,
        };
        assert!(!a.overlaps(&b), "touching boxes should not overlap");
    }

    #[test]
    fn node_box_overlaps_identical() {
        let a = NodeBox {
            ir_node: IrNodeId(0),
            cx: 5.0,
            cy: 5.0,
            width: 10.0,
            height: 10.0,
        };
        let b = NodeBox {
            ir_node: IrNodeId(1),
            cx: 5.0,
            cy: 5.0,
            width: 10.0,
            height: 10.0,
        };
        assert!(a.overlaps(&b), "identical boxes should overlap");
    }

    #[test]
    fn node_box_zero_size() {
        let nb = NodeBox {
            ir_node: IrNodeId(0),
            cx: 5.0,
            cy: 5.0,
            width: 0.0,
            height: 0.0,
        };
        assert!((nb.left() - 5.0).abs() < 1e-9);
        assert!((nb.right() - 5.0).abs() < 1e-9);
        assert!((nb.top() - 5.0).abs() < 1e-9);
        assert!((nb.bottom() - 5.0).abs() < 1e-9);
    }

    // -- count_crossings edge cases --

    #[test]
    fn count_crossings_empty_layers() {
        let layers: Vec<Vec<usize>> = vec![];
        let adj: Vec<Vec<usize>> = vec![];
        assert_eq!(count_crossings(&layers, &adj), 0);
    }

    #[test]
    fn count_crossings_single_layer() {
        let layers = vec![vec![0, 1, 2]];
        let adj = vec![vec![], vec![], vec![]];
        assert_eq!(count_crossings(&layers, &adj), 0);
    }

    #[test]
    fn count_crossings_no_edges_between_layers() {
        let layers = vec![vec![0, 1], vec![2, 3]];
        let adj = vec![vec![], vec![], vec![], vec![]];
        assert_eq!(count_crossings(&layers, &adj), 0);
    }

    #[test]
    fn count_crossings_known_value() {
        // [0, 1] -> [2, 3] with edges 0->3, 1->2: exactly 1 crossing
        let layers = vec![vec![0, 1], vec![2, 3]];
        let adj = vec![vec![3], vec![2], vec![], vec![]];
        assert_eq!(count_crossings(&layers, &adj), 1);
    }

    // -- count_crossings_with scratch reuse --

    #[test]
    fn count_crossings_with_scratch_matches_non_scratch() {
        let layers = vec![vec![0, 1, 2], vec![3, 4, 5], vec![6, 7]];
        let adj = vec![
            vec![4],
            vec![3, 5],
            vec![5],
            vec![6],
            vec![7],
            vec![6, 7],
            vec![],
            vec![],
        ];
        let expected = count_crossings(&layers, &adj);
        let mut scratch = CrossingScratch::new();
        let actual = count_crossings_with(&layers, &adj, &mut scratch);
        assert_eq!(actual, expected);
    }

    // -- resolve_node with ports --

    #[test]
    fn resolve_node_port_endpoint() {
        let mut ir = make_test_ir(&["A", "B"], &[], GraphDirection::TB);
        ir.ports.push(IrPort {
            node: IrNodeId(1),
            name: "p0".to_string(),
            side_hint: IrPortSideHint::Auto,
            span: dummy_span(),
        });
        let result = resolve_node(&ir, IrEndpoint::Port(IrPortId(0)), 2);
        assert_eq!(result, Some(1));
    }

    #[test]
    fn resolve_node_port_out_of_bounds() {
        let ir = make_test_ir(&["A"], &[], GraphDirection::TB);
        // Port index 5 doesn't exist
        let result = resolve_node(&ir, IrEndpoint::Port(IrPortId(5)), 1);
        assert_eq!(result, None);
    }

    #[test]
    fn resolve_node_node_out_of_bounds() {
        let ir = make_test_ir(&["A"], &[], GraphDirection::TB);
        let result = resolve_node(&ir, IrEndpoint::Node(IrNodeId(99)), 1);
        assert_eq!(result, None);
    }

    // -- minimize_crossings with 0 nodes --

    #[test]
    fn minimize_crossings_zero_nodes() {
        let mut budget = 10_000;
        let result = minimize_crossings(&[], &[], &[], 0, 10, &mut budget);
        assert!(result.is_empty());
    }

    // -- assign_layers with empty graph --

    #[test]
    fn assign_layers_empty_graph() {
        let ir = make_test_ir(&[], &[], GraphDirection::TB);
        let config = LayoutConfig::default();
        let graph = LayoutGraph::from_ir(&ir, &config);
        let mut budget = 10_000;
        let layers = assign_layers(&graph, &mut budget);
        assert!(layers.is_empty());
    }

    // -- Ports with different directions and side hints --

    #[test]
    fn port_resolution_all_directions() {
        for &(dir, expected_side) in &[
            (GraphDirection::TB, PortSide::Bottom),
            (GraphDirection::BT, PortSide::Top),
            (GraphDirection::LR, PortSide::Right),
            (GraphDirection::RL, PortSide::Left),
        ] {
            let mut ir = make_test_ir(&["A"], &[], dir);
            ir.ports.push(IrPort {
                node: IrNodeId(0),
                name: "p0".to_string(),
                side_hint: IrPortSideHint::Auto,
                span: dummy_span(),
            });
            let layout = layout_diagram(&ir);
            assert_eq!(layout.ports.len(), 1, "dir={dir:?}");
            assert_eq!(layout.ports[0].side, expected_side, "dir={dir:?}");
        }
    }

    #[test]
    fn port_horizontal_hint_lr() {
        let mut ir = make_test_ir(&["A"], &[], GraphDirection::LR);
        ir.ports.push(IrPort {
            node: IrNodeId(0),
            name: "p0".to_string(),
            side_hint: IrPortSideHint::Horizontal,
            span: dummy_span(),
        });
        let layout = layout_diagram(&ir);
        assert_eq!(layout.ports[0].side, PortSide::Right);
    }

    #[test]
    fn port_horizontal_hint_rl() {
        let mut ir = make_test_ir(&["A"], &[], GraphDirection::RL);
        ir.ports.push(IrPort {
            node: IrNodeId(0),
            name: "p0".to_string(),
            side_hint: IrPortSideHint::Horizontal,
            span: dummy_span(),
        });
        let layout = layout_diagram(&ir);
        assert_eq!(layout.ports[0].side, PortSide::Left);
    }

    #[test]
    fn port_vertical_hint_bt() {
        let mut ir = make_test_ir(&["A"], &[], GraphDirection::BT);
        ir.ports.push(IrPort {
            node: IrNodeId(0),
            name: "p0".to_string(),
            side_hint: IrPortSideHint::Vertical,
            span: dummy_span(),
        });
        let layout = layout_diagram(&ir);
        assert_eq!(layout.ports[0].side, PortSide::Top);
    }

    #[test]
    fn port_vertical_hint_tb() {
        let mut ir = make_test_ir(&["A"], &[], GraphDirection::TB);
        ir.ports.push(IrPort {
            node: IrNodeId(0),
            name: "p0".to_string(),
            side_hint: IrPortSideHint::Vertical,
            span: dummy_span(),
        });
        let layout = layout_diagram(&ir);
        assert_eq!(layout.ports[0].side, PortSide::Bottom);
    }

    #[test]
    fn port_node_out_of_bounds_filtered() {
        let mut ir = make_test_ir(&["A"], &[], GraphDirection::TB);
        ir.ports.push(IrPort {
            node: IrNodeId(99), // doesn't exist
            name: "p0".to_string(),
            side_hint: IrPortSideHint::Auto,
            span: dummy_span(),
        });
        let layout = layout_diagram(&ir);
        assert!(
            layout.ports.is_empty(),
            "out-of-bounds port should be filtered"
        );
    }

    // -- RouteGrid default --

    #[test]
    fn route_grid_default_empty() {
        let grid = RouteGrid::default();
        assert!(grid.vertical_channels.is_empty());
        assert!(grid.horizontal_channels.is_empty());
    }

    // -- LayoutQuality edge cases --

    #[test]
    fn quality_zero_crossings_linear() {
        let ir = make_test_ir(&["A", "B", "C"], &[(0, 1), (1, 2)], GraphDirection::TB);
        let layout = layout_diagram(&ir);
        assert_eq!(layout.quality.crossings, 0);
        assert_eq!(layout.quality.bends, 0);
    }

    #[test]
    fn quality_single_node_zero() {
        let ir = make_test_ir(&["A"], &[], GraphDirection::TB);
        let layout = layout_diagram(&ir);
        assert_eq!(layout.quality.crossings, 0);
        assert_eq!(layout.quality.bends, 0);
        assert!((layout.quality.variance - 0.0).abs() < 1e-9);
        assert!((layout.quality.asymmetry - 0.0).abs() < 1e-9);
        assert!((layout.quality.total_score - 0.0).abs() < 1e-9);
    }

    // -- Degraded flag --

    #[test]
    fn degraded_flag_with_exhausted_budget() {
        let ir = make_test_ir(
            &["A", "B", "C", "D"],
            &[(0, 1), (1, 2), (2, 3)],
            GraphDirection::TB,
        );
        let config = LayoutConfig {
            iteration_budget: 0,
            ..LayoutConfig::default()
        };
        let layout = layout_diagram_with_config(&ir, &config);
        assert!(
            layout.degraded,
            "zero budget should produce degraded layout"
        );
        // But layout should still be valid
        assert_eq!(layout.nodes.len(), 4);
    }

    #[test]
    fn not_degraded_with_ample_budget() {
        let ir = make_test_ir(&["A", "B"], &[(0, 1)], GraphDirection::TB);
        let layout = layout_diagram(&ir);
        assert!(!layout.degraded);
    }

    // -- Edge routing with reversed edges --

    #[test]
    fn reversed_edges_marked_in_routing() {
        // Create a cycle so at least one edge gets reversed
        let ir = make_test_ir(
            &["A", "B", "C"],
            &[(0, 1), (1, 2), (2, 0)],
            GraphDirection::TB,
        );
        let layout = layout_diagram(&ir);
        // At least one edge should be marked reversed
        let reversed_count = layout.edges.iter().filter(|e| e.reversed).count();
        assert!(reversed_count > 0, "cycle should produce reversed edges");
    }

    #[test]
    fn edge_waypoints_always_have_two_points() {
        let ir = make_test_ir(
            &["A", "B", "C"],
            &[(0, 1), (0, 2), (1, 2)],
            GraphDirection::TB,
        );
        let layout = layout_diagram(&ir);
        for (i, edge) in layout.edges.iter().enumerate() {
            assert!(
                edge.waypoints.len() >= 2,
                "edge {i} should have >= 2 waypoints, got {}",
                edge.waypoints.len()
            );
        }
    }

    // -- Cluster with empty members --

    #[test]
    fn cluster_empty_members_filtered() {
        let mut ir = make_test_ir(&["A", "B"], &[(0, 1)], GraphDirection::TB);
        ir.clusters.push(IrCluster {
            id: IrClusterId(0),
            title: None,
            members: vec![], // empty cluster
            span: dummy_span(),
        });
        let layout = layout_diagram(&ir);
        assert!(
            layout.clusters.is_empty(),
            "empty cluster should be filtered out"
        );
    }

    // -- remap_for_direction edge cases --

    #[test]
    fn remap_bt_reverses_y() {
        let mut x = vec![10.0, 20.0];
        let mut y = vec![0.0, 100.0];
        remap_for_direction(&mut x, &mut y, GraphDirection::BT);
        // max_y was 100, so y[0] = 100-0 = 100, y[1] = 100-100 = 0
        assert!((y[0] - 100.0).abs() < 1e-9);
        assert!((y[1] - 0.0).abs() < 1e-9);
        // x unchanged
        assert!((x[0] - 10.0).abs() < 1e-9);
        assert!((x[1] - 20.0).abs() < 1e-9);
    }

    #[test]
    fn remap_lr_swaps_axes() {
        let mut x = vec![10.0, 20.0];
        let mut y = vec![0.0, 100.0];
        remap_for_direction(&mut x, &mut y, GraphDirection::LR);
        assert!((x[0] - 0.0).abs() < 1e-9);
        assert!((x[1] - 100.0).abs() < 1e-9);
        assert!((y[0] - 10.0).abs() < 1e-9);
        assert!((y[1] - 20.0).abs() < 1e-9);
    }

    #[test]
    fn remap_rl_swaps_and_mirrors() {
        let mut x = vec![10.0, 20.0];
        let mut y = vec![0.0, 100.0];
        remap_for_direction(&mut x, &mut y, GraphDirection::RL);
        // After swap: x becomes old y, y becomes old x
        // Then x is mirrored: max_old_y(=100) - old_y
        assert!((x[0] - 100.0).abs() < 1e-9);
        assert!((x[1] - 0.0).abs() < 1e-9);
        assert!((y[0] - 10.0).abs() < 1e-9);
        assert!((y[1] - 20.0).abs() < 1e-9);
    }

    #[test]
    fn remap_tb_noop() {
        let mut x = vec![10.0, 20.0];
        let mut y = vec![0.0, 100.0];
        remap_for_direction(&mut x, &mut y, GraphDirection::TB);
        assert!((x[0] - 10.0).abs() < 1e-9);
        assert!((y[0] - 0.0).abs() < 1e-9);
    }

    // -- LayoutConfig default values --

    #[test]
    fn layout_config_default_all_fields() {
        let c = LayoutConfig::default();
        assert!((c.node_width - 80.0).abs() < 1e-9);
        assert!((c.node_height - 40.0).abs() < 1e-9);
        assert!((c.node_spacing - 30.0).abs() < 1e-9);
        assert!((c.layer_spacing - 60.0).abs() < 1e-9);
        assert!((c.cluster_padding - 10.0).abs() < 1e-9);
        assert_eq!(c.max_crossing_iterations, 24);
        assert_eq!(c.iteration_budget, 10_000);
        assert!(!c.collapse_clusters);
    }

    #[test]
    fn layout_config_from_ir_no_degradation() {
        let ir = make_test_ir(&["A"], &[], GraphDirection::TB);
        let config = LayoutConfig::from_ir(&ir);
        // Should use default values when no degradation
        assert_eq!(config.max_crossing_iterations, 24);
        assert_eq!(config.iteration_budget, 10_000);
        assert!(!config.collapse_clusters);
    }

    // -- Port-based edge routing --

    #[test]
    fn edge_with_port_endpoints() {
        let mut ir = make_test_ir(&["A", "B"], &[], GraphDirection::TB);
        ir.ports.push(IrPort {
            node: IrNodeId(0),
            name: "p0".to_string(),
            side_hint: IrPortSideHint::Auto,
            span: dummy_span(),
        });
        ir.ports.push(IrPort {
            node: IrNodeId(1),
            name: "p1".to_string(),
            side_hint: IrPortSideHint::Auto,
            span: dummy_span(),
        });
        ir.edges.push(IrEdge {
            from: IrEndpoint::Port(IrPortId(0)),
            to: IrEndpoint::Port(IrPortId(1)),
            arrow: "-->".to_string(),
            label: None,
            style_ref: None,
            span: dummy_span(),
        });
        let layout = layout_diagram(&ir);
        assert_eq!(layout.edges.len(), 1);
        assert_eq!(layout.ports.len(), 2);
    }

    // -- Self-loop edge handling --

    #[test]
    fn self_loop_edge_skipped() {
        let ir = make_test_ir(&["A"], &[(0, 0)], GraphDirection::TB);
        let config = LayoutConfig::default();
        let graph = LayoutGraph::from_ir(&ir, &config);
        // Self-loops should be removed from adjacency
        assert!(graph.adj[0].is_empty(), "self-loops should be removed");
    }

    // -- Disconnected components --

    #[test]
    fn disconnected_nodes_all_on_layer_zero() {
        let ir = make_test_ir(&["A", "B", "C", "D", "E"], &[], GraphDirection::TB);
        let layout = layout_diagram(&ir);
        // All disconnected nodes should have the same y
        let y0 = layout.nodes[0].cy;
        for n in &layout.nodes {
            assert!(
                (n.cy - y0).abs() < 1e-9,
                "disconnected nodes should share same y layer"
            );
        }
    }

    #[test]
    fn disconnected_nodes_no_overlap() {
        let ir = make_test_ir(&["A", "B", "C", "D"], &[], GraphDirection::TB);
        let layout = layout_diagram(&ir);
        for i in 0..layout.nodes.len() {
            for j in (i + 1)..layout.nodes.len() {
                assert!(
                    !layout.nodes[i].overlaps(&layout.nodes[j]),
                    "disconnected nodes {i} and {j} overlap"
                );
            }
        }
    }

    // -- Large graph doesn't panic --

    #[test]
    fn large_graph_completes() {
        // 50-node chain should complete without panic
        let labels: Vec<String> = (0..50).map(|i| format!("N{i}")).collect();
        let label_refs: Vec<&str> = labels.iter().map(|s| s.as_str()).collect();
        let edges: Vec<(usize, usize)> = (0..49).map(|i| (i, i + 1)).collect();
        let ir = make_test_ir(&label_refs, &edges, GraphDirection::TB);
        let layout = layout_diagram(&ir);
        assert_eq!(layout.nodes.len(), 50);
        assert_eq!(layout.edges.len(), 49);
        assert!(!layout.degraded);
    }

    // -- Multiple clusters --

    #[test]
    fn multiple_clusters_all_enclose_members() {
        let ir = make_test_ir_with_clusters(
            &["A", "B", "C", "D"],
            &[(0, 1), (2, 3)],
            &[(0, &[0, 1]), (1, &[2, 3])],
            GraphDirection::TB,
        );
        let layout = layout_diagram(&ir);
        assert_eq!(layout.clusters.len(), 2);
        for cluster in &layout.clusters {
            let cid = cluster.ir_cluster.0;
            let member_ids: &[usize] = if cid == 0 { &[0, 1] } else { &[2, 3] };
            for &mid in member_ids {
                let node = &layout.nodes[mid];
                assert!(
                    node.left() >= cluster.x,
                    "node {mid} left outside cluster {cid}"
                );
                assert!(
                    node.right() <= cluster.x + cluster.width,
                    "node {mid} right outside cluster {cid}"
                );
            }
        }
    }

    // -- Edge routing route_grid channels --

    #[test]
    fn route_grid_has_channels_for_edges() {
        let ir = make_test_ir(&["A", "B", "C"], &[(0, 1), (1, 2)], GraphDirection::TB);
        let layout = layout_diagram(&ir);
        // With 2 edges, should have some channels
        assert!(!layout.route_grid.vertical_channels.is_empty());
        assert!(!layout.route_grid.horizontal_channels.is_empty());
    }

    // -- count_crossings_at_with boundary check --

    #[test]
    fn count_crossings_at_first_layer() {
        let layers = vec![vec![0, 1], vec![2, 3]];
        let adj = vec![vec![3], vec![2], vec![], vec![]];
        let mut scratch = CrossingScratch::new();
        let c = count_crossings_at_with(&layers, 0, &adj, &mut scratch);
        // Only checks pair (layer 0, layer 1)
        assert_eq!(c, 1);
    }

    #[test]
    fn count_crossings_at_last_layer() {
        let layers = vec![vec![0, 1], vec![2, 3]];
        let adj = vec![vec![3], vec![2], vec![], vec![]];
        let mut scratch = CrossingScratch::new();
        let c = count_crossings_at_with(&layers, 1, &adj, &mut scratch);
        // Only checks pair (layer 0, layer 1)
        assert_eq!(c, 1);
    }

    // -- PortSide coverage --

    #[test]
    fn port_side_variants_debug() {
        // Ensure all PortSide variants are constructible and debug-printable
        let sides = [
            PortSide::Top,
            PortSide::Bottom,
            PortSide::Left,
            PortSide::Right,
        ];
        for side in &sides {
            let _ = format!("{side:?}");
        }
    }

    // -- DiagramLayout clone --

    #[test]
    fn diagram_layout_clone() {
        let ir = make_test_ir(&["A", "B"], &[(0, 1)], GraphDirection::TB);
        let layout = layout_diagram(&ir);
        let cloned = layout.clone();
        assert_eq!(cloned.nodes.len(), layout.nodes.len());
        assert_eq!(cloned.edges.len(), layout.edges.len());
        assert!((cloned.quality.total_score - layout.quality.total_score).abs() < 1e-12);
    }
}