blockworx/widget/

auto_route.rs

pub use crate::presentation::{Crossing, RouteGeometry};
/// The derived geometry types, re-exported here for the widget layer. The
/// routing behaviour that produces a [`RouteGeometry`] lives below; the
/// authored wire is the document's own [`blockworx_doc::block_model::Route`].
use blockworx_geom::{Pos2, Rect, vec2};
use blockworx_paint::Renderer;
use blockworx_router::{ClosedRouter, WIRE_COST, point::Point};

use std::collections::BTreeMap;

use blockworx_doc::{
    document::{IndexedDocument, chronological},
    geometry::{FracVal, GridPoint, GridVec, Waypoint},
    id::{RouteId, RouteLabelId},
};

use crate::{
    edit::create::PathOrdinal,
    grid::{SHIM, px_point},
    presentation::{
        RouteDirection,
        store::{IdMap, IdMapExt},
    },
    theme::Style,
    widget::{
        edge::RouteEdge,
        materialize::Endpoints,
        segmentkind::SegmentKind,
        waypoint_router::{RouteRequest, SelfCost, TaggedPoint, add_route_cost},
    },
};

/// A horizontal route segment, tagged with the store-order index of the route
/// that owns it. Used only by `compute_crossings`.
#[derive(Clone, Copy, Debug)]
pub struct HEdge {
    pub order: usize,
    pub y: i32,
    pub x_lo: i32,
    pub x_hi: i32,
}

/// A vertical route segment, tagged with the store-order index of the route
/// that owns it. Used only by `compute_crossings`.
#[derive(Clone, Copy, Debug)]
pub struct VEdge {
    pub order: usize,
    pub x: i32,
    pub y_lo: i32,
    pub y_hi: i32,
}

/// Every route order (store index) passing through one crossing *point* on each
/// axis. The set sizes both count the routes at the point and identify them, so
/// a `1`/`1` site is a lone H×V pair and anything busier is a multi-crossing.
#[derive(Default)]
struct CrossingSite {
    h_routes: std::collections::BTreeSet<usize>,
    v_routes: std::collections::BTreeSet<usize>,
}

/// Pure geometry core of crossing detection (no `Block`/`Store` dependency so
/// it can be unit-tested directly). Returns, per route store-order index, the
/// hops that route should draw. A hop is recorded only for a *strict* interior
/// crossing of a horizontal and a vertical segment (so shared endpoints,
/// corners and T-junctions never hop).
///
/// A crossing *point* is resolved to a single orientation so the wires there
/// jump consistently, then *every* route crossing in that orientation draws the
/// same hop (all the verticals bump identically over the horizontals, say):
/// a lone H×V pair hops the later route (render order — the one drawn on top),
/// and any busier point always hops vertically.
pub fn compute_crossings(
    h_edges: &[HEdge],
    v_edges: &[VEdge],
    num_routes: usize,
) -> Vec<Vec<Crossing>> {
    use blockworx_router::event::{Event, EventSense};
    use std::collections::BTreeMap;
    use std::ops::Bound;

    // Pass 1: gather the routes meeting at each crossing point, grouped by axis.
    let mut sites: BTreeMap<(i32, i32), CrossingSite> = BTreeMap::new();

    // Sweep in x using the shared `Event` primitive (the same one the router's
    // `collect_intersections` uses). A horizontal edge is active over its
    // `[x_lo, x_hi]` (Enter/Exit carry its index); a vertical edge at `x = v.x`
    // (Scan carries its index) queries the active horizontals whose row `y` lies
    // strictly in `(v.y_lo, v.y_hi)`. `Event` orders Enter < Scan < Exit at equal
    // `x`, so a horizontal touching `v.x` at a boundary is still active during the
    // scan — but the strict `x`/`y` tests below exclude it, so only strict interior
    // crossings are reported.
    let mut events: Vec<Event<i32, usize>> = Vec::with_capacity(h_edges.len() * 2 + v_edges.len());
    for (i, h) in h_edges.iter().enumerate() {
        events.push(Event::enter(h.x_lo, i));
        events.push(Event::exit(h.x_hi, i));
    }
    for (j, v) in v_edges.iter().enumerate() {
        events.push(Event::scan(v.x, j));
    }
    events.sort();

    // Active horizontal edges, keyed by row `y` → indices into `h_edges`.
    let mut active: BTreeMap<i32, Vec<usize>> = BTreeMap::new();
    for event in events {
        match event.sense() {
            EventSense::Enter => {
                let i = event.cost();
                active.entry(h_edges[i].y).or_default().push(i);
            }
            EventSense::Exit => {
                let i = event.cost();
                if let Some(row) = active.get_mut(&h_edges[i].y) {
                    if let Some(k) = row.iter().position(|&e| e == i) {
                        row.swap_remove(k);
                    }
                    if row.is_empty() {
                        active.remove(&h_edges[i].y);
                    }
                }
            }
            EventSense::Scan => {
                let v = &v_edges[event.cost()];
                for (_y, row) in active.range((Bound::Excluded(v.y_lo), Bound::Excluded(v.y_hi))) {
                    for &i in row {
                        let h = &h_edges[i];
                        // Equal order == same route self-crossing: skip.
                        if h.x_lo < v.x && v.x < h.x_hi && h.order != v.order {
                            let site = sites.entry((v.x, h.y)).or_default();
                            site.h_routes.insert(h.order);
                            site.v_routes.insert(v.order);
                        }
                    }
                }
            }
        }
    }

    // Pass 2: pick each point's orientation and hand the hop to every route that
    // crosses it in that orientation.
    let mut out = vec![Vec::new(); num_routes];
    for ((x, y), site) in sites {
        let pos = GridPoint { x, y };
        // A lone H×V pair hops whichever route was drawn later; anything busier
        // always hops the verticals.
        let lone_pair = site.v_routes.iter().next().zip(site.h_routes.iter().next());
        let vertical = match lone_pair {
            Some((v, h)) if site.h_routes.len() == 1 && site.v_routes.len() == 1 => v > h,
            _ => true,
        };
        let (orientation, hoppers) = if vertical {
            (RouteDirection::Vertical, site.v_routes)
        } else {
            (RouteDirection::Horizontal, site.h_routes)
        };
        for order in hoppers {
            out[order].push(Crossing { pos, orientation });
        }
    }
    out
}

/// A wire as the layers below the document read it: the authored route
/// with the labels hanging off it, which are entities of their own — the
/// bundling twin of `BlockShape`'s pins. Resolved once per borrow, so a
/// renderer, a hit test, and a relayout cannot disagree about which
/// labels a wire carries.
pub struct Wire<'a> {
    pub route: &'a blockworx_doc::block_model::Route,
    pub labels: Vec<(RouteLabelId, FracVal)>,
}

/// A wire's name labels as the geometry layer reads them: the entity to
/// write back to, and the arc length along the solved polyline it sits at.
/// Resolved through the route index in the document's one draw order, so
/// hit-testing, rendering, and re-anchoring all walk the same list.
pub fn route_labels(indexed: &IndexedDocument<'_>, route: RouteId) -> Vec<(RouteLabelId, FracVal)> {
    let Some(entry) = indexed.index.routes.get(&route) else {
        return Vec::new();
    };
    let held: Vec<(RouteLabelId, &blockworx_doc::block_model::RouteLabel)> = entry
        .labels
        .iter()
        .filter_map(|&id| Some((id, indexed.doc.route_label(&id)?)))
        .collect();
    chronological(held.iter().copied())
        .into_iter()
        .filter_map(|id| {
            let label = indexed.doc.route_label(&id)?;
            Some((id, label.pos))
        })
        .collect()
}

/// Which corner of a route sits within `tolerance` of `pos` — the grab a
/// route edit starts from. Waypoints are positional, so the answer is the
/// ordinal the edit session and the emitters both speak.
pub fn hit_waypoint(waypoints: &[Waypoint], pos: Pos2, tolerance: f32) -> Option<PathOrdinal> {
    waypoints.iter().enumerate().find_map(|(index, wp)| {
        (px_point(wp.pos).distance(pos) <= tolerance).then(|| PathOrdinal::new(index))
    })
}

/// The label whose drawn box contains `hover_pos`. `name` is the wire's own
/// name — an unnamed wire measures its faint placeholder instead, so the
/// prompt stays clickable (matching what the renderer draws there).
pub fn hit_text_anchor<R: Renderer>(
    name: &str,
    labels: &[(RouteLabelId, FracVal)],
    geometry: &RouteGeometry,
    hover_pos: Pos2,
    painter: &Style<'_, R>,
) -> Option<RouteLabelId> {
    let text = if name.is_empty() {
        crate::render::ADD_ROUTE_LABEL_PLACEHOLDER
    } else {
        name
    };
    let measured = painter.text_size(text, &painter.theme().route_font);
    labels.iter().find_map(|&(lid, dist)| {
        let pos_and_direction = geometry.map_linear_distance_to_position(dist);
        let center_of_label = pos_and_direction.location
            + match pos_and_direction.direction {
                RouteDirection::Horizontal => vec2(0.0, -measured.y / 2.0 - SHIM / 4.0),
                RouteDirection::Vertical => vec2(measured.y / 2.0 + SHIM / 4.0, 0.0),
            };
        let label_size = match pos_and_direction.direction {
            RouteDirection::Horizontal => measured,
            RouteDirection::Vertical => vec2(measured.y, measured.x),
        };
        Rect::from_center_size(center_of_label, label_size)
            .contains(hover_pos)
            .then_some(lid)
    })
}

/// Where each label sits on the wire — the diamonds a selected route draws.
pub fn text_anchors(labels: &[(RouteLabelId, FracVal)], geometry: &RouteGeometry) -> Vec<Pos2> {
    labels
        .iter()
        .map(|&(_, dist)| geometry.map_linear_distance_to_position(dist).location)
        .collect()
}

/// Each label's current world position, captured before a relayout so
/// [`reanchored`] can put it back where it was instead of letting it slide
/// with the arc length.
pub fn label_anchors(
    labels: &[(RouteLabelId, FracVal)],
    geometry: &RouteGeometry,
) -> Vec<(RouteLabelId, Pos2)> {
    labels
        .iter()
        .map(|&(lid, dist)| (lid, geometry.map_linear_distance_to_position(dist).location))
        .collect()
}

/// Each captured anchor re-projected onto the *current* geometry — the
/// arc lengths a route edit commits. Re-projecting the same screen point
/// keeps a horizontal label at the same X and a vertical one at the same Y
/// (the perpendicular foot shares that coordinate).
pub fn reanchored(
    geometry: &RouteGeometry,
    anchors: &[(RouteLabelId, Pos2)],
) -> Vec<(RouteLabelId, FracVal)> {
    anchors
        .iter()
        .map(|&(lid, pos)| (lid, geometry.distance_along(pos)))
        .collect()
}

/// Solve the router's point list into edge geometry: axis-aligned edges
/// merged while collinear within one segment (two edges from different
/// waypoint legs never merge, even collinear), endpoints from the first
/// and last point, crossings empty until the post-routing pass.
pub fn geometry_from_points(points: &[TaggedPoint]) -> RouteGeometry {
    let mut edges: Vec<(RouteEdge, SegmentKind)> = Vec::new();
    for windows in points.windows(2) {
        let start = windows[0];
        let end = windows[1];
        if start.segment != end.segment {
            continue;
        }
        edges.push((
            RouteEdge {
                start: start.pos.into(),
                end: end.pos.into(),
            },
            start.segment,
        ));
    }
    let start_pos = points
        .first()
        .map_or(GridPoint::default(), |p| GridPoint::from(p.pos));
    let end_pos = points
        .last()
        .map_or(GridPoint::default(), |p| GridPoint::from(p.pos));
    let mut merged_edges = IdMap::default();
    let mut current_edge: Option<(RouteEdge, SegmentKind)> = None;
    for (edge, kind) in edges {
        if let Some((current, current_kind)) = &mut current_edge {
            if *current_kind == kind && current.direction() == edge.direction() {
                current.end = edge.end;
            } else {
                merged_edges.insert_value(current.clone());
                current_edge = Some((edge, kind));
            }
        } else {
            current_edge = Some((edge, kind));
        }
    }
    if let Some((current, _)) = current_edge {
        merged_edges.insert_value(current);
    }
    RouteGeometry {
        edges: merged_edges,
        start_pos,
        end_pos,
        crossings: Vec::new(),
    }
}

/// Non-destructive closed-router reroute: route through the stored waypoint
/// skeleton minus `excluded` (a trim or prune the preview *supposes* without
/// applying — see `PreviewExclusions` in the routing module), additionally
/// skipping inaccessible and position-duplicated corners on a working copy.
/// The authored route is never touched (locks included: they only matter to
/// commit-time trims, never to routing). Replaces `geometry` wholesale —
/// crossings cleared until the post-routing pass — and applies the new edges'
/// occupancy to the router in place.
pub fn reroute_preview_excluding(
    waypoints: &[Waypoint],
    geometry: &mut RouteGeometry,
    ends: Endpoints,
    excluded: &std::collections::HashSet<PathOrdinal>,
    router: &mut ClosedRouter,
) {
    let mut unique_positions = std::collections::HashSet::new();
    let mut wp_ids: Vec<PathOrdinal> = Vec::new();
    let mut wp_positions: BTreeMap<PathOrdinal, Point> = BTreeMap::new();
    for (index, wp) in waypoints.iter().enumerate() {
        let id = PathOrdinal::new(index);
        let pos = wp.pos;
        if excluded.contains(&id)
            || !router.is_accessible(Point::from(pos))
            || !unique_positions.insert(pos)
        {
            continue;
        }
        wp_ids.push(id);
        wp_positions.insert(id, Point::from(pos));
    }
    let path = RouteRequest {
        start: ends.start.into(),
        end: ends.end.into(),
        wp_ids: &wp_ids,
        wp_positions: &wp_positions,
        self_cost: SelfCost::Apply,
    }
    .route(router);
    *geometry = geometry_from_points(&path);
    geometry.start_pos = ends.start;
    geometry.end_pos = ends.end;
    add_route_cost(
        router,
        geometry.edges.iter().map(|(_, edge)| edge),
        WIRE_COST,
    );
}

/// Non-destructive drag preview: reroute as if every stored waypoint were
/// shifted by `waypoint_delta` grid cells, WITHOUT mutating the stored
/// waypoints (the group drag is uncommitted). Only `geometry`'s edges and
/// endpoints are rewritten; the crossings stay as they were (stale until
/// the commit pass recomputes them), and the authored route is untouched.
/// Routes on a frozen [`ClosedRouter`].
pub fn reroute_preview_closed(
    waypoints: &[Waypoint],
    geometry: &mut RouteGeometry,
    ends: Endpoints,
    waypoint_delta: GridVec,
    router: &mut ClosedRouter,
) {
    // Route through an OFFSET COPY of the stored waypoints (never the stored
    // ones); their offset positions were seeded when the graph was built, so
    // they resolve to nodes. No filtering — the drag is uncommitted.
    let offset_positions: BTreeMap<PathOrdinal, Point> = waypoints
        .iter()
        .enumerate()
        .map(|(index, wp)| {
            (
                PathOrdinal::new(index),
                Point::from(wp.pos + waypoint_delta),
            )
        })
        .collect();
    let wp_ids: Vec<PathOrdinal> = (0..waypoints.len()).map(PathOrdinal::new).collect();
    let path = RouteRequest {
        start: ends.start.into(),
        end: ends.end.into(),
        wp_ids: &wp_ids,
        wp_positions: &offset_positions,
        self_cost: SelfCost::Apply,
    }
    .route(router);
    let preview = geometry_from_points(&path);
    add_route_cost(
        router,
        preview.edges.iter().map(|(_, edge)| edge),
        WIRE_COST,
    );
    geometry.edges = preview.edges;
    geometry.start_pos = ends.start;
    geometry.end_pos = ends.end;
}

/// Recompute the visual "hop" decorations for every route in `block` from
/// the routes' *final* geometry. Must run after routing finalizes all
/// routes (e.g. at the end of `Drawing::solve_routes`). Each crossing
/// point resolves to a single orientation and every route crossing it in
/// that orientation gets a matching hop (see [`compute_crossings`]); every
/// present route's hop list is rewritten, so stale hops are always
/// cleared. Routes without a geometry entry contribute nothing but still
/// hold their store-order slot, so the priority order matches the draw
/// order.
pub fn recompute_route_crossings(
    scope_routes: &[RouteId],
    geometries: &mut ahash::HashMap<RouteId, RouteGeometry>,
) {
    let mut h_edges: Vec<HEdge> = Vec::new();
    let mut v_edges: Vec<VEdge> = Vec::new();
    let mut num_routes = 0;
    for (order, id) in scope_routes.iter().enumerate() {
        num_routes = order + 1;
        let Some(geometry) = geometries.get(id) else {
            continue;
        };
        for (_, edge) in geometry.iter_edges() {
            let (s, e) = (edge.start, edge.end);
            if s.y == e.y && s.x != e.x {
                h_edges.push(HEdge {
                    order,
                    y: s.y,
                    x_lo: s.x.min(e.x),
                    x_hi: s.x.max(e.x),
                });
            } else if s.x == e.x && s.y != e.y {
                v_edges.push(VEdge {
                    order,
                    x: s.x,
                    y_lo: s.y.min(e.y),
                    y_hi: s.y.max(e.y),
                });
            }
        }
    }
    let mut per_route = compute_crossings(&h_edges, &v_edges, num_routes);
    for (order, id) in scope_routes.iter().enumerate() {
        if let Some(geometry) = geometries.get_mut(id) {
            geometry.crossings = std::mem::take(&mut per_route[order]);
        }
    }
}

#[cfg(test)]
mod tests {
    use super::{
        Crossing, HEdge, RouteGeometry, VEdge, compute_crossings, label_anchors, reanchored,
    };
    use crate::presentation::{
        RouteDirection, RouteEdge,
        store::{EdgeId, IdMap, IdMapExt},
    };
    use blockworx_doc::{
        fixtures::route_label_id,
        geometry::{FracVal, GridPoint},
        id::RouteLabelId,
    };
    use blockworx_geom::{Pos2, pos2};

    /// A geometry of one straight edge, as an edit's re-materialize would
    /// leave it.
    fn single_edge_geometry(start: GridPoint, end: GridPoint) -> RouteGeometry {
        let mut edges: IdMap<EdgeId, RouteEdge> = IdMap::default();
        edges.insert_value(RouteEdge { start, end });
        RouteGeometry {
            edges,
            start_pos: start,
            end_pos: end,
            crossings: Vec::new(),
        }
    }

    /// One label dropped at `pos` on `geometry` — what the wire-label
    /// emitter would be handed.
    fn label_at(
        geometry: &RouteGeometry,
        pos: Pos2,
    ) -> (RouteLabelId, Vec<(RouteLabelId, FracVal)>) {
        let lid = route_label_id(1);
        (lid, vec![(lid, geometry.distance_along(pos))])
    }

    #[test]
    fn a_horizontal_label_keeps_its_x_when_the_route_is_edited() {
        let g = crate::grid::GRID_SIZE;
        let geometry = single_edge_geometry(GridPoint { x: 0, y: 0 }, GridPoint { x: 10, y: 0 });
        let (lid, labels) = label_at(&geometry, pos2(5.0 * g, 0.0));
        let before = label_anchors(&labels, &geometry);
        let old_x = before[0].1.x;

        // Edit: shift the horizontal run down three cells (a perpendicular drag).
        let geometry = single_edge_geometry(GridPoint { x: 0, y: 3 }, GridPoint { x: 10, y: 3 });
        let after = reanchored(&geometry, &before);

        assert_eq!(after[0].0, lid, "the same label was re-projected");
        let loc = geometry.map_linear_distance_to_position(after[0].1);
        assert!(
            (loc.location.x - old_x).abs() < 0.5,
            "a horizontal label keeps its X: {} -> {}",
            old_x,
            loc.location.x
        );
        assert!(
            (loc.location.y - 3.0 * g).abs() < 0.5,
            "its Y follows the moved wire"
        );
    }

    #[test]
    fn a_vertical_label_keeps_its_y_when_the_route_is_edited() {
        let g = crate::grid::GRID_SIZE;
        let geometry = single_edge_geometry(GridPoint { x: 0, y: 0 }, GridPoint { x: 0, y: 10 });
        let (_, labels) = label_at(&geometry, pos2(0.0, 5.0 * g));
        let before = label_anchors(&labels, &geometry);
        let old_y = before[0].1.y;

        // Edit: shift the vertical run right three cells.
        let geometry = single_edge_geometry(GridPoint { x: 3, y: 0 }, GridPoint { x: 3, y: 10 });
        let after = reanchored(&geometry, &before);

        let loc = geometry.map_linear_distance_to_position(after[0].1);
        assert!(
            (loc.location.y - old_y).abs() < 0.5,
            "a vertical label keeps its Y: {} -> {}",
            old_y,
            loc.location.y
        );
        assert!(
            (loc.location.x - 3.0 * g).abs() < 0.5,
            "its X follows the moved wire"
        );
    }

    fn h(order: usize, y: i32, x_lo: i32, x_hi: i32) -> HEdge {
        HEdge {
            order,
            y,
            x_lo,
            x_hi,
        }
    }
    fn v(order: usize, x: i32, y_lo: i32, y_hi: i32) -> VEdge {
        VEdge {
            order,
            x,
            y_lo,
            y_hi,
        }
    }

    #[test]
    fn later_route_hops_with_correct_orientation() {
        // Route 0 horizontal at y=10 over x 0..20; route 1 vertical at x=10 over y 0..20.
        let out = compute_crossings(&[h(0, 10, 0, 20)], &[v(1, 10, 0, 20)], 2);
        assert!(out[0].is_empty(), "earlier route must not hop");
        assert_eq!(
            out[1],
            vec![Crossing {
                pos: GridPoint { x: 10, y: 10 },
                orientation: RouteDirection::Vertical,
            }],
            "later (vertical) route hops over the earlier one"
        );
    }

    #[test]
    fn hopping_segment_orientation_follows_the_later_route() {
        // Now the later route owns the horizontal segment.
        let out = compute_crossings(&[h(1, 10, 0, 20)], &[v(0, 10, 0, 20)], 2);
        assert!(out[0].is_empty());
        assert_eq!(
            out[1],
            vec![Crossing {
                pos: GridPoint { x: 10, y: 10 },
                orientation: RouteDirection::Horizontal,
            }]
        );
    }

    #[test]
    fn multi_crossing_hops_every_vertical() {
        // A horizontal route (order 1) crosses two co-linear vertical routes
        // (orders 0 and 2) at the same point: a multi-crossing, so it resolves
        // vertical and *both* verticals hop identically over the horizontal.
        let hop = |order| {
            (
                order,
                vec![Crossing {
                    pos: GridPoint { x: 10, y: 10 },
                    orientation: RouteDirection::Vertical,
                }],
            )
        };
        let out = compute_crossings(&[h(1, 10, 0, 20)], &[v(0, 10, 0, 20), v(2, 10, 0, 20)], 3);
        assert_eq!(out[hop(0).0], hop(0).1, "vertical route 0 hops");
        assert_eq!(out[hop(2).0], hop(2).1, "vertical route 2 hops");
        assert!(out[1].is_empty(), "the horizontal route is hopped over");
    }

    #[test]
    fn t_junction_does_not_hop() {
        // Vertical segment ends exactly on the horizontal line (y_lo == h.y): not
        // a strict interior crossing, so no hop.
        let out = compute_crossings(&[h(0, 10, 0, 20)], &[v(1, 10, 10, 20)], 2);
        assert!(out.iter().all(std::vec::Vec::is_empty));
    }

    #[test]
    fn shared_corner_does_not_hop() {
        // Segments meet at a shared endpoint (a route bend): no hop.
        let out = compute_crossings(&[h(0, 10, 0, 10)], &[v(1, 10, 10, 20)], 2);
        assert!(out.iter().all(std::vec::Vec::is_empty));
    }

    #[test]
    fn self_crossing_same_route_is_skipped() {
        // Same store-order index on both segments => ambiguous self-crossing, skipped.
        let out = compute_crossings(&[h(0, 10, 0, 20)], &[v(0, 10, 0, 20)], 1);
        assert!(out[0].is_empty());
    }
}