blockworx_editor/widget/

materialize.rs

//! Deriving a route's edge geometry from its ordered corner list.
//!
//! Under the explicit-path model a route is fully described by its ordered
//! corner sequence `[start_pos, waypoint…, end_pos]` — waypoint insertion order
//! *is* the polyline order. These helpers extract the canonical corner set from
//! a raw polyline and read a route's ordered corner points; the straight-or-route
//! materialization (which turns those corners back into edges, invoking the
//! router only for blocked/non-colinear legs) builds on them.

use std::collections::{BTreeMap, HashSet};

use blockworx_doc::geometry::{GridPoint, Waypoint};
use blockworx_router::block::{Block as ObstacleRect, ROUTE_GUTTER};
use blockworx_router::{ClosedRouter, Direction, WIRE_COST, direction_between};

use crate::presentation::RouteEdge;
use crate::presentation::RouteGeometry;
use crate::presentation::store::{EdgeId, IdMap, IdMapExt};
use crate::widget::waypoint_router::add_route_cost;

/// A route's authored corners in the presentation layer's grid vocabulary —
/// the one conversion the materialization pass makes, so the leg walk below
/// speaks a single coordinate type.
fn corner_positions(waypoints: &[Waypoint]) -> Vec<GridPoint> {
    waypoints.iter().map(|wp| wp.pos).collect()
}

/// The obstacle rectangles of a block, for the cheap "does a straight wire cross
/// a block?" test that decides whether a leg can stay straight. Mirrors exactly
/// the rects `build_closed_router_for_block` feeds to the router as blocks, so a
/// straight leg judged clear here is the same one the router would leave alone —
/// but without paying to build the routing graph (the point of the fast load path).
///
/// Rects are indexed by the rows and columns they span, so `blocked`/`accessible`
/// only test the rects that could possibly hit the query line — not all of them.
/// A linear scan here is quadratic across a whole document's routes (each leg
/// scans every block), which showed up as ~20s of load overhead at scale.
pub struct Obstacles {
    rects: Vec<ObstacleRect>,
    by_row: BTreeMap<i32, Vec<usize>>,
    by_col: BTreeMap<i32, Vec<usize>>,
}

impl Obstacles {
    pub fn new(rects: Vec<ObstacleRect>) -> Self {
        let mut by_row: BTreeMap<i32, Vec<usize>> = BTreeMap::new();
        let mut by_col: BTreeMap<i32, Vec<usize>> = BTreeMap::new();
        for (i, r) in rects.iter().enumerate() {
            for y in r.top_left.y.raw()..=r.bottom_right.y.raw() {
                by_row.entry(y).or_default().push(i);
            }
            for x in r.top_left.x.raw()..=r.bottom_right.x.raw() {
                by_col.entry(x).or_default().push(i);
            }
        }
        Self {
            rects,
            by_row,
            by_col,
        }
    }

    /// Whether the axis-aligned wire `a → b` crosses any obstacle. Same result as
    /// [`ClosedRouter::is_wire_blocked`], but only the rects spanning the wire's
    /// row (horizontal wire) or column (vertical wire) are tested.
    pub fn blocked(&self, a: GridPoint, b: GridPoint) -> bool {
        let candidates = if a.y == b.y {
            self.by_row.get(&a.y)
        } else if a.x == b.x {
            self.by_col.get(&a.x)
        } else {
            None
        };
        candidates
            .into_iter()
            .flatten()
            .any(|&i| self.rects[i].intersects_edge(a, b))
    }

    /// Whether the axis-aligned wire `a → b` hugs any obstacle (runs alongside an
    /// edge within the routing gutter).
    ///
    /// A hugging wire runs *beside* an edge rather than over it, so the index is
    /// queried a gutter wide either side of the wire: a rect with an edge within
    /// `ROUTE_GUTTER` of row `y` spans one of the rows `y-gutter ..= y+gutter`,
    /// and so is in one of their buckets. A rect spanning several of them is
    /// tested more than once, which costs less than the dedup would.
    pub fn hugs(&self, a: GridPoint, b: GridPoint) -> bool {
        let (index, at) = if a.y == b.y {
            (&self.by_row, a.y)
        } else if a.x == b.x {
            (&self.by_col, a.x)
        } else {
            return false;
        };
        index
            .range(at - ROUTE_GUTTER..=at + ROUTE_GUTTER)
            .flat_map(|(_, bucket)| bucket)
            .any(|&i| self.rects[i].hugs_wire(a, b, ROUTE_GUTTER))
    }

    /// Whether `p` lies outside every obstacle (a waypoint inside one is dropped).
    pub fn accessible(&self, p: GridPoint) -> bool {
        !self
            .by_row
            .get(&p.y)
            .into_iter()
            .flatten()
            .any(|&i| self.rects[i].contains(p.into()))
    }
}

fn axis_aligned(a: GridPoint, b: GridPoint) -> bool {
    a.x == b.x || a.y == b.y
}

/// A route's resolved (snapped) endpoints for one solve or
/// materialization pass.
#[derive(Clone, Copy)]
pub struct Endpoints {
    pub start: GridPoint,
    pub end: GridPoint,
}

/// Rebuild the edge geometry of a wire whose authored corners are `stored`,
/// keeping every straight (axis-aligned, unblocked) leg as a single edge and
/// routing ONLY the legs that are non-colinear or blocked. `start`/`end` are the
/// resolved grid endpoints. Straight legs never touch the router, so an
/// unaffected route (all legs straight) is reconstructed byte-identically with
/// zero pathfinding.
///
/// When a leg needs routing, `router` must be `Some` (already built and occupied
/// by the other routes); the leg's new bends are spliced into the corner list so
/// the "every corner is a waypoint" invariant is restored. If a leg needs routing
/// and `router` is `None`, no geometry is written and `None` is returned so the
/// caller can build the router and retry. Interior waypoints that fall inside an
/// obstacle are dropped (only on the routing path, where `router` is `Some`).
///
/// Returns the corner list the materialization promotes — the polyline the
/// gesture's commit stores, which the caller pushes as an op. Nothing here
/// writes the document.
pub fn materialize_route(
    stored: &[Waypoint],
    geometry: &mut RouteGeometry,
    ends: Endpoints,
    obstacles: &Obstacles,
    mut router: Option<&mut ClosedRouter>,
) -> Option<Vec<Waypoint>> {
    // Ordered corners: start, each waypoint (drop inaccessible ones when routing),
    // then end. Waypoint order is path order.
    let mut corners: Vec<GridPoint> = Vec::with_capacity(stored.len() + 2);
    corners.push(ends.start);
    for pos in corner_positions(stored) {
        if router.is_some() && !obstacles.accessible(pos) {
            continue;
        }
        corners.push(pos);
    }
    corners.push(ends.end);

    // Walk the legs, emitting the resulting polyline. Straight legs contribute a
    // single hop; routed legs contribute their solved sub-path.
    let mut polyline: Vec<GridPoint> = vec![corners[0]];
    let mut incoming: Option<Direction> = None;
    for pair in corners.windows(2) {
        let (a, b) = (pair[0], pair[1]);
        if a == b {
            continue;
        }
        if axis_aligned(a, b) && !obstacles.blocked(a, b) && !obstacles.hugs(a, b) {
            polyline.push(b);
            incoming = direction_between(a.into(), b.into());
            continue;
        }
        let r = router.as_mut()?;
        let (subpath, outgoing) = r.route_leg(a.into(), b.into(), incoming);
        if subpath.len() >= 2 {
            polyline.extend(subpath[1..].iter().map(|&p| GridPoint::from(p)));
        } else {
            polyline.push(b);
        }
        incoming = outgoing;
    }

    let locked = locked_corners(stored);
    let path = corners_of(&polyline);
    let promoted = write_geometry(geometry, ends, &path, &locked);

    if let Some(r) = router.as_mut() {
        add_route_cost(r, geometry.iter_edges().map(|(_, e)| e), WIRE_COST);
    }
    Some(promoted)
}

/// Rebuild a wire's edges from its corner list (start + corners + end) as
/// axis-aligned segments WITHOUT the router: a straight leg is one edge; a
/// diagonal leg (its two endpoints share no row or column) becomes an L via a
/// single bend. It never consults obstacles and never promotes bends to
/// waypoints, so dragging a segment or corner repositions the wire directly and
/// never triggers an autoroute — the segment goes exactly where the user puts
/// it. The corner list is a read, so per-frame recomputation stays
/// accumulation-free and the route editor's drag keeps owning it.
///
/// A *connector* leg — the first leg (from the start anchor to its corner) and
/// the last (from the last corner to the end anchor) — is bent so the segment
/// touching the pin runs along the pin's horizontal E/W stub: the first leg goes
/// horizontal-first (leaving the pin), the last goes vertical-first (so its final
/// segment enters the pin horizontally). This keeps the ends one cell clear of the
/// block instead of hugging its gutter. Interior legs keep an incoming-axis bend so
/// they can't double back.
pub fn materialize_corners_direct(
    waypoints: &[GridPoint],
    geometry: &mut RouteGeometry,
    ends: Endpoints,
) {
    let mut corners: Vec<GridPoint> = Vec::with_capacity(waypoints.len() + 2);
    corners.push(ends.start);
    corners.extend_from_slice(waypoints);
    corners.push(ends.end);

    let last_leg = corners.len().saturating_sub(2);
    let has_waypoints = corners.len() > 2;
    let mut polyline: Vec<GridPoint> = vec![corners[0]];
    let mut incoming: Option<Direction> = None;
    for (i, pair) in corners.windows(2).enumerate() {
        let (a, b) = (pair[0], pair[1]);
        if a == b {
            continue;
        }
        if axis_aligned(a, b) {
            polyline.push(b);
        } else {
            let horizontal_first = if has_waypoints && i == 0 {
                true // first connector: leave the start pin along its horizontal stub
            } else if has_waypoints && i == last_leg {
                false // last connector: enter the end pin along its horizontal stub
            } else {
                !matches!(incoming, Some(Direction::North | Direction::South))
            };
            let bend = if horizontal_first {
                GridPoint { x: b.x, y: a.y }
            } else {
                GridPoint { x: a.x, y: b.y }
            };
            polyline.push(bend);
            polyline.push(b);
        }
        incoming = direction_between(polyline[polyline.len() - 2].into(), b.into());
    }

    let path = corners_of(&polyline);
    let mut edges: IdMap<EdgeId, RouteEdge> = IdMap::default();
    for w in path.windows(2) {
        edges.insert_value(RouteEdge {
            start: w[0],
            end: w[1],
        });
    }
    geometry.edges = edges;
    geometry.start_pos = ends.start;
    geometry.end_pos = ends.end;
}

/// Overwrite the solved geometry from the canonical corner polyline `path`
/// (`[start, corners…, end]`) and return the waypoint list that polyline
/// promotes: interior corners in path order, `locked` iff they coincide with
/// a previously locked corner. The list is the caller's to push as an op —
/// the solver writes geometry, never the document.
fn write_geometry(
    geometry: &mut RouteGeometry,
    ends: Endpoints,
    path: &[GridPoint],
    locked: &HashSet<GridPoint>,
) -> Vec<Waypoint> {
    geometry.edges = edges_of(path);
    geometry.start_pos = ends.start;
    geometry.end_pos = ends.end;
    interior_waypoints(path, locked)
}

/// The polyline's segments as presentation edges.
fn edges_of(path: &[GridPoint]) -> IdMap<EdgeId, RouteEdge> {
    let mut edges: IdMap<EdgeId, RouteEdge> = IdMap::default();
    for w in path.windows(2) {
        edges.insert_value(RouteEdge {
            start: w[0],
            end: w[1],
        });
    }
    edges
}

/// The corners a canonical polyline `[start, corners…, end]` implies as
/// waypoints, in path order, `locked` iff one already sat there.
fn interior_waypoints(path: &[GridPoint], locked: &HashSet<GridPoint>) -> Vec<Waypoint> {
    if path.len() <= 2 {
        return Vec::new();
    }
    path[1..path.len() - 1]
        .iter()
        .map(|&pos| Waypoint {
            pos,
            locked: locked.contains(&pos),
        })
        .collect()
}

/// Where the user pinned a corner, so a rebuild can keep it pinned.
fn locked_corners(waypoints: &[Waypoint]) -> HashSet<GridPoint> {
    waypoints
        .iter()
        .filter(|wp| wp.locked)
        .map(|wp| wp.pos)
        .collect()
}

/// Reduce a polyline to its corners: drop adjacent duplicate points and any
/// point collinear with its neighbours (a redundant interior point on a straight
/// run). Keeps the first and last points and only the true direction-change
/// vertices — the canonical corner set the model stores as waypoints. Idempotent.
pub fn corners_of(points: &[GridPoint]) -> Vec<GridPoint> {
    let mut out: Vec<GridPoint> = Vec::with_capacity(points.len());
    for &p in points {
        if out.last() == Some(&p) {
            continue;
        }
        if let [.., a, b] = out[..]
            && collinear(a, b, p)
        {
            out.pop();
        }
        out.push(p);
    }
    out
}

/// Every corner of the wire's polyline as a waypoint, in path order — the
/// invariant the explicit-path model relies on. Derives the list from the
/// route's current edge geometry: each interior bend becomes a waypoint,
/// preserving the `locked` flag of any existing waypoint already at that position
/// (so user-pinned corners stay pinned) and marking the rest structural
/// (`locked: false`). The endpoints are never waypoints. The returned list is
/// what the gesture's commit stores; the geometry is rebuilt in place.
pub fn promote_corners_to_waypoints(
    stored: &[Waypoint],
    geometry: &mut RouteGeometry,
) -> Vec<Waypoint> {
    let corners = geometry_corners(geometry);
    let locked = locked_corners(stored);

    // Rebuild the edges from the canonical corners as well, not just the
    // waypoints. `corners_of` collapses a 180° reversal (an overshoot the wire
    // doubles straight back on), which strict waypoint routing and a literal
    // route edit can leave in `edges`. Rebuilding only the waypoints would let
    // that spike linger in the geometry — showing a malformed wire that "fixes
    // itself" only after a reload rebuilds edges from the clean waypoints — so
    // keep the two in sync here. Real 90° bends are direction changes, not
    // collinear, so obstacle-avoidance geometry is preserved untouched.
    geometry.edges = edges_of(&corners);
    interior_waypoints(&corners, &locked)
}

/// The canonical corner polyline of solved geometry, endpoints included.
pub fn geometry_corners(geometry: &RouteGeometry) -> Vec<GridPoint> {
    let mut polyline = vec![geometry.start_pos];
    polyline.extend(geometry.iter_edges().map(|(_, e)| e.end));
    polyline.push(geometry.end_pos);
    corners_of(&polyline)
}

/// Whether `b` lies on the straight line through `a` and `c` (zero cross
/// product). For the axis-aligned corners we deal with, this means `a`, `b`, `c`
/// share a row or column.
fn collinear(a: GridPoint, b: GridPoint, c: GridPoint) -> bool {
    (b.x - a.x) as i64 * (c.y - a.y) as i64 == (b.y - a.y) as i64 * (c.x - a.x) as i64
}

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

    use crate::edit::geometry::{backtracking_ordinals, pruned_waypoints};

    fn g(x: i32, y: i32) -> GridPoint {
        GridPoint { x, y }
    }

    fn wp(x: i32, y: i32) -> Waypoint {
        Waypoint {
            pos: GridPoint { x, y },
            locked: false,
        }
    }

    /// The authored corners of a wire as a materialization pass reads them —
    /// the post-load state: corner waypoints present, edges empty.
    fn loaded_route(waypoints: &[(i32, i32)]) -> Vec<Waypoint> {
        waypoints.iter().map(|&(x, y)| wp(x, y)).collect()
    }

    fn edges_double_back(geometry: &RouteGeometry) -> bool {
        let edges: Vec<_> = geometry
            .iter_edges()
            .map(|(_, e)| (e.start, e.end))
            .collect();
        edges.windows(2).any(|w| {
            let (ax, ay) = (w[0].1.x - w[0].0.x, w[0].1.y - w[0].0.y);
            let (bx, by) = (w[1].1.x - w[1].0.x, w[1].1.y - w[1].0.y);
            (ay == 0 && by == 0 && (ax > 0) != (bx > 0))
                || (ax == 0 && bx == 0 && (ay > 0) != (by > 0))
        })
    }

    #[test]
    fn promote_erases_a_backtracking_spike_from_the_edges() {
        use crate::edit::create::PathOrdinal;
        use crate::widget::segmentkind::SegmentKind;
        use crate::widget::waypoint_router::TaggedPoint;
        use blockworx_router::point::Point;

        let tp = |segment, x, y| TaggedPoint {
            segment,
            pos: Point::from(g(x, y)),
        };
        // Overshoot: run east to the waypoint at x=10, then straight back west to
        // x=5 — a 180° reversal split across the two waypoint legs, so the solve
        // keeps both edges (they never merge across a leg boundary).
        let w = PathOrdinal::new(0);
        let path = [
            tp(SegmentKind::StartToWaypoint(w), 0, 0),
            tp(SegmentKind::StartToWaypoint(w), 10, 0),
            tp(SegmentKind::WaypointToEnd(w), 10, 0),
            tp(SegmentKind::WaypointToEnd(w), 5, 0),
        ];
        let stored = loaded_route(&[(10, 0)]);
        let mut geometry = crate::widget::auto_route::geometry_from_points(&path);
        assert!(
            edges_double_back(&geometry),
            "setup: the solve kept the reversal spike in the edges"
        );

        let promoted = promote_corners_to_waypoints(&stored, &mut geometry);
        assert!(
            !edges_double_back(&geometry),
            "promote collapsed the spike in the edges"
        );
        assert!(promoted.is_empty(), "and dropped the overshoot waypoint");
    }

    #[test]
    fn corners_of_drops_collinear_interior_points() {
        // A run east then a run south: only the bend at (2,0) survives.
        let pts = [g(0, 0), g(1, 0), g(2, 0), g(2, 1), g(2, 2)];
        assert_eq!(corners_of(&pts), vec![g(0, 0), g(2, 0), g(2, 2)]);
    }

    #[test]
    fn corners_of_drops_adjacent_duplicates() {
        let pts = [g(0, 0), g(0, 0), g(3, 0), g(3, 0)];
        assert_eq!(corners_of(&pts), vec![g(0, 0), g(3, 0)]);
    }

    #[test]
    fn corners_of_is_idempotent() {
        let pts = [g(0, 0), g(1, 0), g(2, 0), g(2, 3), g(5, 3), g(5, 3)];
        let once = corners_of(&pts);
        assert_eq!(corners_of(&once), once);
    }

    #[test]
    fn promote_makes_every_bend_a_waypoint() {
        use crate::edit::create::PathOrdinal;
        use crate::widget::segmentkind::SegmentKind;
        use crate::widget::waypoint_router::TaggedPoint;
        use blockworx_router::point::Point;

        let tp = |x: i32, y: i32| TaggedPoint {
            segment: SegmentKind::StartToEnd,
            pos: Point::from(GridPoint { x, y }),
        };
        // Z-shape: east, south, east — two bends at (3,0) and (3,3).
        let path = [tp(0, 0), tp(3, 0), tp(3, 3), tp(6, 3)];
        let stored = loaded_route(&[]);
        let mut geometry = crate::widget::auto_route::geometry_from_points(&path);
        assert!(stored.is_empty());
        assert_ne!(
            PathOrdinal::new(0),
            PathOrdinal::new(1),
            "ordinals name distinct corners"
        );

        let promoted = promote_corners_to_waypoints(&stored, &mut geometry);

        assert_eq!(corner_positions(&promoted), vec![g(3, 0), g(3, 3)]);
        assert!(promoted.iter().all(|wp| !wp.locked));
    }

    #[test]
    fn straight_legs_materialize_without_a_router() {
        let stored = loaded_route(&[(3, 0)]);
        let mut geometry = RouteGeometry::default();
        // (0,0) →H (3,0) →V (3,4): both legs axis-aligned and clear.
        let done = materialize_route(
            &stored,
            &mut geometry,
            Endpoints {
                start: g(0, 0),
                end: g(3, 4),
            },
            &Obstacles::new(vec![]),
            None,
        );
        assert!(done.is_some(), "a straight route needs no router");
        let edges: Vec<(GridPoint, GridPoint)> = geometry
            .iter_edges()
            .map(|(_, e)| (e.start, e.end))
            .collect();
        assert_eq!(edges, vec![(g(0, 0), g(3, 0)), (g(3, 0), g(3, 4))]);
    }

    #[test]
    fn a_blocked_leg_defers_when_no_router() {
        let stored = loaded_route(&[]);
        let mut geometry = RouteGeometry::default();
        // A block straddling the straight run (0,0)→(10,0).
        let obstacles = Obstacles::new(vec![ObstacleRect {
            top_left: g(4, -2).into(),
            bottom_right: g(6, 2).into(),
        }]);
        let done = materialize_route(
            &stored,
            &mut geometry,
            Endpoints {
                start: g(0, 0),
                end: g(10, 0),
            },
            &obstacles,
            None,
        );
        assert!(
            done.is_none(),
            "a blocked straight leg must defer to the router"
        );
    }

    #[test]
    fn direct_relay_draws_straight_legs_and_leaves_its_corners() {
        let corners = [g(0, 5)];
        let mut geometry = RouteGeometry::default();
        materialize_corners_direct(
            &corners,
            &mut geometry,
            Endpoints {
                start: g(0, 0),
                end: g(5, 5),
            },
        );
        let edges: Vec<(GridPoint, GridPoint)> = geometry
            .iter_edges()
            .map(|(_, e)| (e.start, e.end))
            .collect();
        assert_eq!(edges, vec![(g(0, 0), g(0, 5)), (g(0, 5), g(5, 5))]);
        // The direct relay rebuilds edges only; the corner list it was handed
        // is a read, so the drag still owns it.
        assert_eq!(corners, [g(0, 5)]);
    }

    #[test]
    fn direct_relay_l_bends_a_diagonal_leg_without_a_router() {
        let mut geometry = RouteGeometry::default();
        materialize_corners_direct(
            &[g(3, 4)],
            &mut geometry,
            Endpoints {
                start: g(0, 0),
                end: g(3, 8),
            },
        );
        assert!(
            geometry
                .iter_edges()
                .all(|(_, e)| e.start.x == e.end.x || e.start.y == e.end.y),
            "every relayed edge is axis-aligned — an L, never a diagonal"
        );
        assert!(
            geometry.iter_edges().count() >= 2,
            "the diagonal leg produced a bend"
        );
    }

    #[test]
    fn a_non_colinear_leg_defers_when_no_router() {
        // Waypoint diagonal from the start: the first leg is not axis-aligned.
        let stored = loaded_route(&[(3, 4)]);
        let mut geometry = RouteGeometry::default();
        let done = materialize_route(
            &stored,
            &mut geometry,
            Endpoints {
                start: g(0, 0),
                end: g(3, 8),
            },
            &Obstacles::new(vec![]),
            None,
        );
        assert!(
            done.is_none(),
            "a non-colinear leg must defer to the router"
        );
    }

    /// The backtracking prune the commit pass applies and the preview
    /// supposes: one policy, [`crate::edit::geometry::backtracking_ordinals`],
    /// read here through the corner list it prunes.
    fn pruned(
        waypoints: &[(i32, i32)],
        start: GridPoint,
        end: GridPoint,
    ) -> (Vec<GridPoint>, bool) {
        let stored: Vec<Waypoint> = waypoints.iter().map(|&(x, y)| wp(x, y)).collect();
        let doomed = backtracking_ordinals(&stored, start, end);
        (
            corner_positions(&pruned_waypoints(&stored, &doomed)),
            !doomed.is_empty(),
        )
    }

    #[test]
    fn removes_a_waypoint_the_wire_doubles_back_on() {
        // start (0,0) → wp (10,0) → end (5,0): the wire runs east to x=10, then
        // west to x=5 — a 180° reversal at the waypoint, which must be dropped.
        let (kept, removed) = pruned(&[(10, 0)], g(0, 0), g(5, 0));
        assert!(removed);
        assert!(kept.is_empty());
    }

    #[test]
    fn keeps_a_real_corner_and_a_straight_through_pin() {
        // A 90° corner is not a reversal.
        let (kept, removed) = pruned(&[(10, 0)], g(0, 0), g(10, 5));
        assert!(!removed);
        assert_eq!(kept, vec![g(10, 0)]);
        // A waypoint between its neighbours on a straight run (0°) pins the wire's
        // row; it is not a reversal, so it survives.
        let (kept, removed) = pruned(&[(5, 0)], g(0, 0), g(10, 0));
        assert!(!removed);
        assert_eq!(kept.len(), 1);
    }

    #[test]
    fn cascades_after_a_removal_exposes_a_new_reversal() {
        // start (0,0) → (10,0) → (3,0) → end (5,0). Dropping the (10,0) overshoot
        // leaves (0,0) → (3,0) → (5,0), a straight run, so (3,0) stays.
        let (kept, removed) = pruned(&[(10, 0), (3, 0)], g(0, 0), g(5, 0));
        assert!(removed);
        assert_eq!(kept, vec![g(3, 0)]);
    }
}