facett-core 0.1.18

//! **Legibility at scale** — the shared screen-space toolbox that makes a 100 000-node
//! graph (or a 1 000 000-pin map) something a human can actually *read*.
//!
//! Speed and legibility are different problems and they need different cures. The GPU
//! cloud lane ([`crate::render::gpu::graphcloud`], feature `wgpu`) answers "the frame
//! takes 33 ms" by not tessellating on the CPU. It does **nothing** for "there are
//! 40 000 labels stacked on 400 pixels and 900 000 edges have merged into one grey
//! rectangle". That is this module.
//!
//! Three primitives, all pure (no egui painting, no GPU), all deterministic, all
//! headless-testable:
//!
//! | primitive | the defect it cures |
//! |---|---|
//! | [`ScreenGrid`] | hover/pick that linear-scans every node on every mouse move |
//! | [`place_labels`] | labels that overplot into unreadable mush |
//! | [`thin_edges`] | a hairball where every pixel is saturated and structure is invisible |
//!
//! # The honesty fields
//!
//! The map side (`facett-geomap`'s `PointGrid`) shipped with a doc comment promising
//! "the cost scales with what is on screen, not the dataset size" — and it did not: the
//! lattice spanned the whole world, so a regional dataset collapsed into a corner of it
//! and a city-block query still swept 11 000-point cells. **Nothing was red**, because
//! the claim was prose.
//!
//! So every structure here reports the work it actually did as DATA:
//! [`NearestHit::candidates`] (points distance-tested), [`LabelPlacement::considered`]
//! / [`LabelPlacement::collision_tests`], [`EdgeThinResult::peak_density_before`] /
//! [`EdgeThinResult::peak_density`]. A test asserts on those numbers instead of on a
//! sentence, and the same lie cannot be told twice.
//!
//! # Determinism
//!
//! Every function is a pure function of its inputs, ordered by explicit sort keys that
//! end in the input index — never by `HashMap` iteration. Two identical frames produce
//! byte-identical output, so a golden/robot oracle can assert exact contents (FC-7).

use egui::{Pos2, Rect, Vec2};

// ─────────────────────────────────────────────────────────────────────────────
// 1. ScreenGrid — the screen-space spatial index for picking + hover
// ─────────────────────────────────────────────────────────────────────────────

/// The average number of points a bin should hold. The lattice is sized from the
/// data's bounding box and the point count so this holds *at any extent* — which is
/// exactly the property `facett-geomap`'s world-spanning lattice did not have.
const TARGET_PER_CELL: f32 = 8.0;

/// A uniform **screen-space** bin lattice over a set of projected points, for
/// `O(neighbourhood)` nearest / rect queries.
///
/// # Why a second grid, when `facett-geomap::PointGrid` exists (L5)
///
/// They index different spaces for different lifetimes and are not
/// interchangeable. `PointGrid` bins `f64` **Mercator world** units and is built
/// **once per dataset** — it survives pan/zoom because world coordinates do.
/// `ScreenGrid` bins `f32` **screen pixels** and is rebuilt when the projection
/// changes, because a screen coordinate is only meaningful for one camera. A graph
/// pane picks in screen space (a chip's hit radius is a pixel radius, not a world
/// radius), and a *label* collision is by definition a pixel collision — so this is
/// the lattice both of those want. The sizing *discipline* (span the DATA bbox, not
/// some fixed universe) is the shared lesson, and it is applied here from the start.
///
/// Empty input builds an empty grid whose queries return nothing — never a panic and
/// never a divide by zero.
#[derive(Clone, Debug)]
pub struct ScreenGrid {
    /// Min corner of the indexed bounding box.
    origin: Pos2,
    /// Bin edge length in px (always `> 0`).
    cell: f32,
    cols: usize,
    rows: usize,
    /// Row-major `cols × rows` buckets of point indices, each in ascending order.
    bins: Vec<Vec<u32>>,
    len: usize,
}

/// What a [`ScreenGrid::nearest`] probe found — and, crucially, **how much work it
/// did** to find it. `candidates` is the anti-lie field: a linear scan reports
/// `candidates == len`, an honest index reports a small neighbourhood.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct NearestHit {
    /// Index into the `points` slice the grid was built from.
    pub index: u32,
    /// Distance in px from the probe to that point.
    pub dist: f32,
    /// How many points were actually distance-tested to produce this answer.
    pub candidates: usize,
}

impl ScreenGrid {
    /// Build a lattice over `points`, auto-sizing the bin so the average occupancy is
    /// [`TARGET_PER_CELL`] **over the data's own bounding box**.
    #[must_use]
    pub fn build(points: &[Pos2]) -> Self {
        Self::build_inner(points, None)
    }

    /// Build with an explicit bin edge in px — for label/edge lattices where the cell
    /// must match a known collision scale rather than the point density.
    #[must_use]
    pub fn build_with_cell(points: &[Pos2], cell: f32) -> Self {
        Self::build_inner(points, Some(cell))
    }

    fn build_inner(points: &[Pos2], forced_cell: Option<f32>) -> Self {
        let finite = |p: &Pos2| p.x.is_finite() && p.y.is_finite();
        let mut min = Pos2::new(f32::INFINITY, f32::INFINITY);
        let mut max = Pos2::new(f32::NEG_INFINITY, f32::NEG_INFINITY);
        let mut n_finite = 0usize;
        for p in points.iter().filter(|p| finite(p)) {
            n_finite += 1;
            min.x = min.x.min(p.x);
            min.y = min.y.min(p.y);
            max.x = max.x.max(p.x);
            max.y = max.y.max(p.y);
        }
        if n_finite == 0 {
            return Self {
                origin: Pos2::ZERO,
                cell: 1.0,
                cols: 0,
                rows: 0,
                bins: Vec::new(),
                len: points.len(),
            };
        }
        // A degenerate extent (every point identical, or one point) still has to build
        // a finite, lossless grid — so the span is floored, never zero.
        let span_x = (max.x - min.x).max(1.0);
        let span_y = (max.y - min.y).max(1.0);
        let cell = match forced_cell {
            Some(c) if c.is_finite() && c > 0.0 => c,
            _ => {
                let target_cells = (n_finite as f32 / TARGET_PER_CELL).max(1.0);
                // Square-ish bins: area / target_cells, side = sqrt.
                ((span_x * span_y) / target_cells).sqrt().max(1e-3)
            }
        };
        // Cap the lattice so a pathological cell/extent ratio cannot allocate the world.
        const MAX_CELLS: usize = 1 << 22;
        let mut cols = ((span_x / cell).ceil() as usize + 1).max(1);
        let mut rows = ((span_y / cell).ceil() as usize + 1).max(1);
        let mut cell = cell;
        while cols.saturating_mul(rows) > MAX_CELLS {
            cell *= 2.0;
            cols = ((span_x / cell).ceil() as usize + 1).max(1);
            rows = ((span_y / cell).ceil() as usize + 1).max(1);
        }
        let mut bins: Vec<Vec<u32>> = vec![Vec::new(); cols * rows];
        for (i, p) in points.iter().enumerate() {
            if !finite(p) {
                continue;
            }
            let gx = (((p.x - min.x) / cell).floor() as isize).clamp(0, cols as isize - 1) as usize;
            let gy = (((p.y - min.y) / cell).floor() as isize).clamp(0, rows as isize - 1) as usize;
            bins[gy * cols + gx].push(i as u32);
        }
        Self { origin: min, cell, cols, rows, bins, len: points.len() }
    }

    /// How many points were indexed (including non-finite ones, which are stored
    /// nowhere and can never be returned by a query).
    #[must_use]
    pub fn len(&self) -> usize {
        self.len
    }

    /// Is the index empty?
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// `(cols, rows)` of the lattice.
    #[must_use]
    pub fn dims(&self) -> (usize, usize) {
        (self.cols, self.rows)
    }

    /// The bin edge in px.
    #[must_use]
    pub fn cell(&self) -> f32 {
        self.cell
    }

    /// The **fullest bin's** occupancy — the locality oracle. A lattice laid over the
    /// wrong extent collapses the whole dataset into a handful of bins and this number
    /// approaches `len`; a correctly-sized one keeps it near [`TARGET_PER_CELL`].
    #[must_use]
    pub fn max_occupancy(&self) -> usize {
        self.bins.iter().map(Vec::len).max().unwrap_or(0)
    }

    fn cell_of(&self, p: Pos2) -> (isize, isize) {
        (
            ((p.x - self.origin.x) / self.cell).floor() as isize,
            ((p.y - self.origin.y) / self.cell).floor() as isize,
        )
    }

    /// Every indexed point whose bin overlaps `r`, appended to `out` in ascending
    /// index order. `out` is **not** cleared (so a caller can accumulate); the return
    /// value is how many were appended.
    ///
    /// This is a bin-granular query: it can return points just outside `r` (same bin),
    /// never miss one inside it. Callers that need exactness re-test the returned
    /// points — which is cheap, because there are few.
    pub fn query_rect(&self, r: Rect, out: &mut Vec<u32>) -> usize {
        if self.cols == 0 || self.rows == 0 {
            return 0;
        }
        let (x0, y0) = self.cell_of(r.min);
        let (x1, y1) = self.cell_of(r.max);
        let x0 = x0.clamp(0, self.cols as isize - 1) as usize;
        let x1 = x1.clamp(0, self.cols as isize - 1) as usize;
        let y0 = y0.clamp(0, self.rows as isize - 1) as usize;
        let y1 = y1.clamp(0, self.rows as isize - 1) as usize;
        // A rect entirely off one side of the lattice clamps to an edge band; reject it
        // outright so an off-screen query costs nothing rather than sweeping the edge.
        if r.max.x < self.origin.x
            || r.max.y < self.origin.y
            || r.min.x > self.origin.x + self.cols as f32 * self.cell
            || r.min.y > self.origin.y + self.rows as f32 * self.cell
        {
            return 0;
        }
        let before = out.len();
        for gy in y0..=y1 {
            for gx in x0..=x1 {
                out.extend_from_slice(&self.bins[gy * self.cols + gx]);
            }
        }
        out[before..].sort_unstable();
        out.len() - before
    }

    /// The **nearest** indexed point to `probe` within `max_dist` px, or `None`.
    ///
    /// Expanding-ring search from the probe's own bin outward: a ring is only visited
    /// while it could still contain something closer than the best found so far, so the
    /// cost tracks the local density and the search radius — **not** the dataset size.
    /// That claim is checkable: [`NearestHit::candidates`] reports exactly how many
    /// points were distance-tested.
    ///
    /// Ties resolve to the lowest index, so the answer is deterministic.
    #[must_use]
    pub fn nearest(&self, points: &[Pos2], probe: Pos2, max_dist: f32) -> Option<NearestHit> {
        if self.cols == 0 || self.rows == 0 || !probe.x.is_finite() || !probe.y.is_finite() {
            return None;
        }
        let max_dist = if max_dist.is_finite() && max_dist > 0.0 { max_dist } else { return None };
        let (cx, cy) = self.cell_of(probe);
        let max_ring = ((max_dist / self.cell).ceil() as isize).max(0);
        let mut best: Option<(u32, f32)> = None;
        let mut candidates = 0usize;
        for ring in 0..=max_ring {
            // Nothing in ring r can be nearer than (r-1)·cell (the probe may sit at the
            // far corner of its own bin). Once that floor exceeds the best hit, stop.
            if let Some((_, d)) = best {
                if (ring as f32 - 1.0) * self.cell > d {
                    break;
                }
            }
            let visit = |gx: isize, gy: isize, best: &mut Option<(u32, f32)>, cand: &mut usize| {
                if gx < 0 || gy < 0 || gx >= self.cols as isize || gy >= self.rows as isize {
                    return;
                }
                for &i in &self.bins[gy as usize * self.cols + gx as usize] {
                    let Some(p) = points.get(i as usize) else { continue };
                    *cand += 1;
                    let d = probe.distance(*p);
                    if d > max_dist {
                        continue;
                    }
                    match best {
                        Some((bi, bd)) if *bd < d || (*bd == d && *bi <= i) => {}
                        _ => *best = Some((i, d)),
                    }
                }
            };
            if ring == 0 {
                visit(cx, cy, &mut best, &mut candidates);
            } else {
                for gx in (cx - ring)..=(cx + ring) {
                    visit(gx, cy - ring, &mut best, &mut candidates);
                    visit(gx, cy + ring, &mut best, &mut candidates);
                }
                for gy in (cy - ring + 1)..=(cy + ring - 1) {
                    visit(cx - ring, gy, &mut best, &mut candidates);
                    visit(cx + ring, gy, &mut best, &mut candidates);
                }
            }
        }
        best.map(|(index, dist)| NearestHit { index, dist, candidates })
    }
}

// ─────────────────────────────────────────────────────────────────────────────
// 2. Label collision — the half of the MapLibre lesson the pins were missing
// ─────────────────────────────────────────────────────────────────────────────

/// One label that *wants* to be drawn. The caller has already projected the anchor
/// and measured the text.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct LabelCandidate {
    /// Where the label's box is centred if it gets its first choice, in screen px.
    pub anchor: Pos2,
    /// Measured text extent in px (`galley.size()`).
    pub size: Vec2,
    /// Higher wins a contested pixel. Degree, centrality, zoom-importance — the
    /// caller's ranking. Ties break to the lower input index, so it is deterministic.
    pub priority: f32,
    /// Never suppressed: the selection, the hovered node, a search hit. Pinned labels
    /// are placed before everything else and are placed even if they must overlap
    /// another pinned label (the user asked for exactly these).
    pub pinned: bool,
}

impl LabelCandidate {
    /// A plain unpinned candidate.
    #[must_use]
    pub fn new(anchor: Pos2, size: Vec2, priority: f32) -> Self {
        Self { anchor, size, priority, pinned: false }
    }

    /// Mark as never-suppressed (selection / hover / search hit).
    #[must_use]
    pub fn pinned(mut self, on: bool) -> Self {
        self.pinned = on;
        self
    }
}

/// A label that won its pixels.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct PlacedLabel {
    /// Index into the candidate slice.
    pub index: usize,
    /// The box it occupies, in screen px — **already** offset to whichever alternate
    /// position was free. Paint the text centred in this rect.
    pub rect: Rect,
    /// Which position in the ladder was taken: `0` = the anchor itself, `1..` = an
    /// alternate. A frame where everything is `0` had no contention.
    pub slot: u8,
}

/// The outcome of one frame's label placement, with the work it did.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct LabelPlacement {
    /// The labels to draw, in placement order (pinned first, then priority desc,
    /// then input index) — deterministic.
    pub placed: Vec<PlacedLabel>,
    /// Candidates that lost every position in the ladder.
    pub suppressed: usize,
    /// Candidates that were even looked at — an off-viewport candidate is rejected
    /// before any collision work, so this is the "cost tracks the screen" witness.
    pub considered: usize,
    /// Rect-vs-rect overlap tests performed. A quadratic placer reports `~n²/2`; the
    /// grid-backed one reports a small multiple of `considered`.
    pub collision_tests: usize,
}

impl LabelPlacement {
    /// The fraction of considered labels that got drawn, `0.0..=1.0`.
    #[must_use]
    pub fn density(&self) -> f32 {
        if self.considered == 0 { 0.0 } else { self.placed.len() as f32 / self.considered as f32 }
    }

    /// `state_json`-friendly summary (the observable a robot/matrix row asserts on).
    #[must_use]
    pub fn state_json(&self) -> serde_json::Value {
        serde_json::json!({
            "placed": self.placed.len(),
            "suppressed": self.suppressed,
            "considered": self.considered,
            "collision_tests": self.collision_tests,
        })
    }
}

/// How aggressive the placer is.
#[derive(Clone, Copy, Debug)]
pub struct PlaceOpts {
    /// Extra padding around each label box in px, so neighbours do not merely *touch*.
    pub pad: f32,
    /// Try alternate positions (below / above / right / left of the anchor) when the
    /// first choice collides — Mapbox's "variable label placement". Off = one shot.
    pub variable: bool,
    /// Suppress labels whose box is not fully inside the viewport. Off = a label may
    /// hang over the edge (still clipped by the painter).
    pub clip_to_viewport: bool,
    /// **Work budget** — stop considering candidates after this many on-screen ones.
    /// `0` = unlimited.
    ///
    /// A screen has a hard ceiling on how many labels can physically fit
    /// (`viewport area / label area`); past a few multiples of it, every further
    /// candidate is a guaranteed rejection that still pays for a collision query. At
    /// 30 000 on-screen nodes that tail was measured at tens of milliseconds per frame
    /// — a legibility cure that costs the frame rate is not a cure.
    ///
    /// Because candidates are walked in **priority order**, truncating takes the tail,
    /// never the labels the user cares about: the pinned ones and the highest-ranked
    /// ones are already placed before the budget runs out. Truncated candidates are
    /// neither placed nor counted as suppressed — they were never considered — so
    /// `placed + suppressed == considered` still holds exactly.
    pub max_considered: usize,

    /// **Density ceiling** — stop PLACING after this many labels, however many more
    /// would still physically fit. `0` = unlimited (only collision decides).
    ///
    /// Collision alone answers "do these two share pixels?", and the honest answer on a
    /// dense map is that a great many labels do not — so the placer packs them shoulder
    /// to shoulder and the result is a legible *text field* with a map somewhere behind
    /// it. MEASURED on korp-ui over Stockholm at zoom 12.7 (1258×728 canvas): **255**
    /// non-overlapping street names — one per 3 591 px² — and the picture was still
    /// unreadable. Every pair passed the collision test. (That pane published no ink
    /// figure; the box coverage that goes with those 255 is a lower bound of ~32 %, and
    /// the honest end-to-end measurement is in
    /// `facett_map::layer::LABEL_MIN_PX2_EACH`.)
    ///
    /// So the second law is areal, and it is the caller's to set from its own pane:
    /// `max_placed = viewport.area() / min_px²_per_label`. Cartographic practice puts
    /// that divisor in the low tens of thousands of px²; see
    /// `facett_map::layer::LABEL_MIN_PX2_EACH` for the shipped derivation.
    ///
    /// **Pinned labels are exempt** — they are the answer to the user's click, and a
    /// budget must not eat the one label that was asked for.
    ///
    /// Candidates dropped by the budget WERE considered (they were walked, ranked and
    /// looked at), so they count as [`suppressed`](LabelPlacement::suppressed) and
    /// `placed + suppressed == considered` still holds exactly. Because the walk is in
    /// priority order, the budget takes the tail — never the place names.
    pub max_placed: usize,
}

impl Default for PlaceOpts {
    fn default() -> Self {
        Self { pad: 2.0, variable: true, clip_to_viewport: false, max_considered: 0, max_placed: 0 }
    }
}

/// **Greedy screen-space label collision.** Walks the candidates in priority order and
/// gives each the first box in its ladder that no already-placed label occupies.
///
/// This is the same discipline `facett-geomap`'s pin clustering applies to *markers*,
/// applied to *text*: the threshold is "these would visually collide", which is a
/// screen distance, so it works at every zoom and latitude without a second tuning.
/// The difference is what happens on a collision — a pile of markers **merges** into a
/// count badge (no information is lost, it is summarised), while a pile of labels can
/// only **drop** the losers, because overlapping text is strictly less readable than
/// one label. Hence the priority: the caller decides who is worth reading.
///
/// Cost: one [`ScreenGrid`] over the anchors plus a bin-local overlap test per
/// candidate — `O(considered)` with a small constant, not `O(n²)`.
#[must_use]
pub fn place_labels(cands: &[LabelCandidate], viewport: Rect, opts: PlaceOpts) -> LabelPlacement {
    let mut out = LabelPlacement::default();
    if cands.is_empty() {
        return out;
    }
    // Order: pinned first, then priority descending, then input index. The final key is
    // the index, so the order is total and no HashMap/float tie can perturb it.
    let mut order: Vec<usize> = (0..cands.len()).collect();
    order.sort_by(|&a, &b| {
        let (ca, cb) = (&cands[a], &cands[b]);
        cb.pinned
            .cmp(&ca.pinned)
            .then(cb.priority.total_cmp(&ca.priority))
            .then(a.cmp(&b))
    });

    // The occupancy lattice: bins sized to the widest label so a box spans at most a
    // 2×2 neighbourhood and the overlap test stays local.
    let max_w = cands.iter().map(|c| c.size.x + 2.0 * opts.pad).fold(1.0f32, f32::max);
    let max_h = cands.iter().map(|c| c.size.y + 2.0 * opts.pad).fold(1.0f32, f32::max);
    let cell = max_w.max(max_h).max(1.0);
    let cols = ((viewport.width() / cell).ceil() as usize + 2).max(1);
    let rows = ((viewport.height() / cell).ceil() as usize + 2).max(1);
    let mut bins: Vec<Vec<u32>> = vec![Vec::new(); cols * rows];
    let mut placed_rects: Vec<Rect> = Vec::with_capacity(cands.len());

    // The lattice covers the viewport, but a label box may hang OFF it (its anchor is
    // allowed within half a box of the edge, and variable placement pushes further).
    // Bin indices are therefore CLAMPED into range, never skipped: a rect that pokes
    // outside is registered in the edge bin instead of nowhere. Skipping was a real
    // bug — two labels overlapping only in the region beyond the lattice consulted no
    // shared bin, collided, and both drew. The pixel oracle caught it at peak 2.
    let bin_of = |p: Pos2| -> (usize, usize) {
        let gx = ((p.x - viewport.min.x) / cell).floor();
        let gy = ((p.y - viewport.min.y) / cell).floor();
        (
            (gx.max(0.0) as usize).min(cols - 1),
            (gy.max(0.0) as usize).min(rows - 1),
        )
    };

    for &i in &order {
        if opts.max_considered > 0 && out.considered >= opts.max_considered {
            break;
        }
        let c = &cands[i];
        if !c.anchor.x.is_finite() || !c.anchor.y.is_finite() {
            out.suppressed += 1;
            continue;
        }
        let half = (c.size + Vec2::splat(2.0 * opts.pad)) * 0.5;
        // Off-viewport candidates cost nothing: rejected before any collision work.
        if !viewport.expand2(half).contains(c.anchor) {
            continue;
        }
        out.considered += 1;

        // ── THE DENSITY CEILING ──────────────────────────────────────────────
        // Asked AFTER `considered` is incremented and BEFORE any collision work, so
        // the budget costs nothing per rejected candidate and the accounting still
        // closes (`placed + suppressed == considered`). A pinned label is exempt.
        if !c.pinned && opts.max_placed > 0 && out.placed.len() >= opts.max_placed {
            out.suppressed += 1;
            continue;
        }

        // The ladder: the anchor, then four displaced alternates (Mapbox variable
        // placement). A pinned label takes its anchor unconditionally.
        let ladder: &[Vec2] = if opts.variable {
            &[
                Vec2::ZERO,
                Vec2::new(0.0, 1.0),
                Vec2::new(0.0, -1.0),
                Vec2::new(1.0, 0.0),
                Vec2::new(-1.0, 0.0),
            ]
        } else {
            &[Vec2::ZERO]
        };

        let mut chosen: Option<(Rect, u8)> = None;
        for (slot, dir) in ladder.iter().enumerate() {
            let centre = c.anchor + Vec2::new(dir.x * (half.x * 2.0 + 1.0), dir.y * (half.y * 2.0 + 1.0));
            let r = Rect::from_center_size(centre, half * 2.0);
            if opts.clip_to_viewport && !viewport.contains_rect(r) {
                continue;
            }
            if c.pinned && slot == 0 {
                chosen = Some((r, 0));
                break;
            }
            // Bin-local overlap test — only the ≤ 3×3 neighbourhood is consulted.
            let (bx0, by0) = bin_of(r.min);
            let (bx1, by1) = bin_of(r.max);
            let mut collides = false;
            'scan: for gy in by0..=by1 {
                for gx in bx0..=bx1 {
                    for &pi in &bins[gy * cols + gx] {
                        out.collision_tests += 1;
                        if placed_rects[pi as usize].intersects(r) {
                            collides = true;
                            break 'scan;
                        }
                    }
                }
            }
            if !collides {
                chosen = Some((r, slot as u8));
                break;
            }
        }

        match chosen {
            Some((rect, slot)) => {
                let pi = placed_rects.len() as u32;
                placed_rects.push(rect);
                let (bx0, by0) = bin_of(rect.min);
                let (bx1, by1) = bin_of(rect.max);
                for gy in by0..=by1 {
                    for gx in bx0..=bx1 {
                        bins[gy * cols + gx].push(pi);
                    }
                }
                out.placed.push(PlacedLabel { index: i, rect, slot });
            }
            None => out.suppressed += 1,
        }
    }
    out
}

/// The **pixel oracle** for a label placement: the highest number of label boxes
/// covering any single pixel of `viewport`, computed by actually rasterizing the boxes
/// into a coverage buffer at `scale` px per sample.
///
/// `1` means no two labels share a pixel — the thing "collision avoidance" claims. An
/// unthinned frame of the same data reports the true pile depth, so the assertion has
/// somewhere to go red from. Independent of the placer's own bookkeeping on purpose:
/// it reads the *result*, not the algorithm.
#[must_use]
pub fn max_label_overlap(rects: &[Rect], viewport: Rect, scale: f32) -> u32 {
    let scale = if scale.is_finite() && scale > 0.0 { scale } else { 1.0 };
    let w = ((viewport.width() / scale).ceil() as usize).clamp(1, 4096);
    let h = ((viewport.height() / scale).ceil() as usize).clamp(1, 4096);
    let mut cover = vec![0u32; w * h];
    let mut peak = 0u32;
    // Nearest-pixel-centre coverage (`round`, not floor/ceil). A rasterizer lights the
    // pixels whose centres the box covers, so two boxes with a real gap between them
    // land on disjoint pixels. floor/ceil would inflate every box by up to a pixel on
    // each side and report a phantom overlap for merely *adjacent* labels — an oracle
    // that fires on correct output is worse than no oracle.
    for r in rects {
        let x0 = (((r.min.x - viewport.min.x) / scale).round() as isize).clamp(0, w as isize) as usize;
        let x1 = (((r.max.x - viewport.min.x) / scale).round() as isize).clamp(0, w as isize) as usize;
        let y0 = (((r.min.y - viewport.min.y) / scale).round() as isize).clamp(0, h as isize) as usize;
        let y1 = (((r.max.y - viewport.min.y) / scale).round() as isize).clamp(0, h as isize) as usize;
        for y in y0..y1 {
            for x in x0..x1 {
                let c = &mut cover[y * w + x];
                *c += 1;
                peak = peak.max(*c);
            }
        }
    }
    peak
}

// ─────────────────────────────────────────────────────────────────────────────
// 3. Density-aware edge thinning — the hairball cure
// ─────────────────────────────────────────────────────────────────────────────

/// How many direction buckets an edge's angle is quantized into. Edges are thinned
/// *within* a direction bucket, so a bundle of near-parallel filaments collapses while
/// an edge crossing them at a different angle survives — the structure that makes a
/// hairball readable is exactly the structure that differs in direction.
const DIR_BUCKETS: usize = 4;

/// Thinning knobs.
#[derive(Clone, Copy, Debug)]
pub struct EdgeThinOpts {
    /// Lattice bin edge in px. Density is measured, and the keep-quota applied, per
    /// `(bin, direction)` bucket.
    pub cell: f32,
    /// How many edges survive per `(bin, direction)` bucket. `0` keeps none (other
    /// than the always-keeps); a large value keeps everything.
    pub keep_per_bucket: usize,
}

impl Default for EdgeThinOpts {
    fn default() -> Self {
        Self { cell: 24.0, keep_per_bucket: 3 }
    }
}

/// The outcome of one frame's edge thinning, with the density it actually achieved.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct EdgeThinResult {
    /// Indices of the edges to draw, ascending — so the paint order (and therefore the
    /// over-draw) is identical to the unthinned pass minus the dropped ones.
    pub keep: Vec<u32>,
    /// How many were dropped.
    pub dropped: usize,
    /// Edges considered (on-viewport). Off-screen edges are rejected first, so the
    /// cost tracks the screen.
    pub considered: usize,
    /// Peak segments-per-bin **before** thinning — how black the worst pixel was.
    pub peak_density_before: usize,
    /// Peak segments-per-bin **after**. The measurable claim: this is bounded by
    /// `keep_per_bucket · DIR_BUCKETS` plus the always-keeps.
    pub peak_density: usize,
}

impl EdgeThinResult {
    /// `state_json`-friendly summary.
    #[must_use]
    pub fn state_json(&self) -> serde_json::Value {
        serde_json::json!({
            "kept": self.keep.len(),
            "dropped": self.dropped,
            "considered": self.considered,
            "peak_density_before": self.peak_density_before,
            "peak_density": self.peak_density,
        })
    }
}

/// A **monotonic `u32` key** for an `f32`: `a <= b` iff `key(a) <= key(b)` for every
/// finite value (and NaN sorts last). Lets a hot sort use plain integer ordering
/// instead of a float comparator, which is both faster and immune to the
/// already-sorted-input trap that made the edge bench read 9x cheaper than reality.
#[inline]
fn monotonic_key(v: f32) -> u32 {
    let b = v.to_bits();
    if b & 0x8000_0000 != 0 { !b } else { b ^ 0x8000_0000 }
}

/// Walk the lattice bins a segment crosses (clamped to the `cols × rows` viewport
/// lattice), calling `f` with each row-major bin index. A cheap DDA at cell
/// resolution — the ink a segment deposits, not just where its midpoint fell.
fn walk_bins(
    a: Pos2,
    b: Pos2,
    origin: Pos2,
    cell: f32,
    cols: usize,
    rows: usize,
    mut f: impl FnMut(usize),
) {
    let inv = 1.0 / cell;
    let (ax, ay) = ((a.x - origin.x) * inv, (a.y - origin.y) * inv);
    let (bx, by) = ((b.x - origin.x) * inv, (b.y - origin.y) * inv);
    let steps = ((bx - ax).abs().max((by - ay).abs()).ceil() as usize).clamp(1, 8192);
    // INCREMENTAL stepping: one add per axis per step. The obvious `t = s/steps` +
    // lerp form costs a divide and two multiply-adds per step, and this walk is the
    // whole cost of `thin_edges` (it is proportional to the ink, not the edge count) —
    // 120 000 viewport-spanning segments cross ~55 cells each, i.e. ~6600000 steps per
    // frame, so the per-step constant is the number that matters.
    let inv_steps = 1.0 / steps as f32;
    let (dx, dy) = ((bx - ax) * inv_steps, (by - ay) * inv_steps);
    let (mut x, mut y) = (ax, ay);
    let (fcols, frows) = (cols as f32, rows as f32);
    let mut last = usize::MAX;
    for _ in 0..=steps {
        if x >= 0.0 && y >= 0.0 && x < fcols && y < frows {
            let idx = y as usize * cols + x as usize;
            if idx != last {
                f(idx);
                last = idx;
            }
        }
        x += dx;
        y += dy;
    }
}

/// **Density-aware edge thinning — an ink budget per screen cell.**
///
/// Every on-screen segment is walked across the viewport lattice at `cell` resolution
/// and its ink is charged to each bin it crosses, per quantized direction. An edge is
/// drawn only if **every** bin along its path still has room in its
/// `keep_per_bucket` quota for that direction; otherwise it is dropped. Edges flagged
/// in `always` (the selected path, a highlighted cycle, the hovered node's incident
/// edges) are drawn unconditionally, and are charged to the budget so they crowd out
/// bulk edges rather than adding on top of them.
///
/// Two design choices worth stating, because the obvious alternatives are worse:
///
/// - **Charge the whole path, not the midpoint.** Binning an edge by its midpoint is
///   cheap and wrong: a long edge crossing the pane deposits ink over hundreds of
///   cells while being quota-charged to one. A hairball of long edges would then pass
///   every counter while rendering exactly as black as before — and the pixel oracle
///   ([`edge_ink_profile`]) is what catches that, which is why this function is
///   written to satisfy the *pixels* and not the bookkeeping.
/// - **Quota per direction.** A pile of near-parallel filaments is redundant; an edge
///   crossing them at another angle is the structure you are trying to see. Quantizing
///   into [`DIR_BUCKETS`] means a saturated bin still admits a transversal edge.
///
/// And why not "just draw fewer edges at random": a uniform 1-in-k sample thins the
/// sparse regions exactly as hard as the dense ones, destroying the readable parts of
/// the graph to fix the unreadable parts. An ink budget leaves a sparse region
/// completely untouched — a bin under quota keeps everything — and only bites where the
/// pane was already saturated.
///
/// `weight` ranks who gets the budget first (edge weight, betweenness, whatever the
/// caller has); pass an empty slice for "all equal", in which case the lower index
/// wins. Fully deterministic: one global sort ending in the edge index, and a dense
/// lattice rather than a `HashMap`, so nothing depends on hash order.
#[must_use]
pub fn thin_edges(
    segments: &[(Pos2, Pos2)],
    weight: &[f32],
    always: &[bool],
    viewport: Rect,
    opts: EdgeThinOpts,
) -> EdgeThinResult {
    let mut out = EdgeThinResult::default();
    if segments.is_empty() {
        return out;
    }
    let cell = if opts.cell.is_finite() && opts.cell > 0.0 { opts.cell } else { 24.0 };
    let cols = ((viewport.width() / cell).ceil() as usize + 1).clamp(1, 8192);
    let rows = ((viewport.height() / cell).ceil() as usize + 1).clamp(1, 8192);
    let origin = viewport.min;

    let finite = |p: Pos2| p.x.is_finite() && p.y.is_finite();
    let dir_of = |a: Pos2, b: Pos2| -> usize {
        let folded = (b.y - a.y).atan2(b.x - a.x).rem_euclid(std::f32::consts::PI);
        (((folded / std::f32::consts::PI) * DIR_BUCKETS as f32).floor() as usize).min(DIR_BUCKETS - 1)
    };

    // Which edges are even on screen — the cost-tracks-the-screen gate.
    let mut on_screen: Vec<u32> = Vec::with_capacity(segments.len());
    for (i, &(a, b)) in segments.iter().enumerate() {
        if finite(a) && finite(b) && viewport.intersects(Rect::from_two_pos(a, b)) {
            on_screen.push(i as u32);
        }
    }
    out.considered = on_screen.len();
    if out.considered == 0 {
        return out;
    }

    let w = |i: u32| weight.get(i as usize).copied().unwrap_or(0.0);
    let keep_always = |i: u32| always.get(i as usize).copied().unwrap_or(false);

    // Budget order: the always-keeps first (they are non-negotiable and must charge
    // the budget before anyone else spends it), then heaviest-first, ties to the lower
    // index — a total order, so the survivors are a pure function of the input.
    //
    // The keys are MATERIALIZED into an integer triple and sorted with `sort_unstable`
    // rather than compared through closures. The comparator version measured 47 ms for
    // 120 000 edges against 5 ms for 100 000 — a 9x gap that was not the data. The
    // 100 000 arm had an EMPTY weight slice, so every key compared equal, the input was
    // already index-ordered, and the merge sort detected one long run and ran in O(n).
    // In other words the cheap-looking arm was measuring a best case that no real caller
    // ever hits, and the honest cost was hiding behind four bounds-checked slice reads
    // per comparison. `sort_unstable` on a plain `(u8, u32, u32)` has no such trap, and
    // the index in the last position keeps the order total (so `sort_unstable`'s lack of
    // stability cannot change the result).
    let mut order: Vec<(u8, u32, u32)> = on_screen
        .iter()
        .map(|&i| (u8::from(!keep_always(i)), !monotonic_key(w(i)), i))
        .collect();
    order.sort_unstable();
    let order: Vec<u32> = order.into_iter().map(|(_, _, i)| i).collect();

    // ONE DDA walk per segment. The obvious implementation walks three times — once to
    // measure the before-density, once to spend the budget, once to measure the
    // after-density — and the walk IS the cost of this function (it is proportional to
    // the ink, not to the edge count). All three are folded into the single pass below:
    // `before` is charged unconditionally, `occ`/`after` only when the edge survives.
    let quota = opts.keep_per_bucket as u32;
    let mut occ = vec![0u32; cols * rows * DIR_BUCKETS];
    let mut before = vec![0u32; cols * rows];
    let mut after = vec![0u32; cols * rows];
    let (mut peak_before, mut peak_after) = (0u32, 0u32);
    let mut keep: Vec<u32> = Vec::with_capacity(order.len());
    let mut path: Vec<usize> = Vec::new();
    for &i in &order {
        let (a, b) = segments[i as usize];
        let d = dir_of(a, b);
        path.clear();
        walk_bins(a, b, origin, cell, cols, rows, |idx| path.push(idx));
        for &idx in &path {
            before[idx] += 1;
            peak_before = peak_before.max(before[idx]);
        }
        let forced = keep_always(i);
        let fits = forced || (quota > 0 && path.iter().all(|&idx| occ[idx * DIR_BUCKETS + d] < quota));
        if !fits {
            continue;
        }
        for &idx in &path {
            occ[idx * DIR_BUCKETS + d] += 1;
            after[idx] += 1;
            peak_after = peak_after.max(after[idx]);
        }
        keep.push(i);
    }
    keep.sort_unstable();
    out.dropped = out.considered - keep.len();
    out.peak_density_before = peak_before as usize;
    out.peak_density = peak_after as usize;
    out.keep = keep;
    out
}

/// The **pixel oracle** for edge legibility: rasterize the segments into a `w × h`
/// coverage buffer over `viewport` and return `(lit_px, peak_hits, saturated_px)` —
/// how much of the pane has ink, the deepest pile on one pixel, and how many pixels are
/// covered `>= saturate` times (i.e. are pure hairball, carrying no structure).
///
/// A readable frame has a small `saturated_px`; a hairball's is most of the pane. This
/// reads the *rendered result*, so it is red when the thinning silently stops working
/// even if every counter in [`EdgeThinResult`] still looks plausible.
#[must_use]
pub fn edge_ink_profile(
    segments: &[(Pos2, Pos2)],
    keep: &[u32],
    viewport: Rect,
    saturate: u32,
) -> (usize, u32, usize) {
    let w = (viewport.width().ceil() as usize).clamp(1, 2048);
    let h = (viewport.height().ceil() as usize).clamp(1, 2048);
    let mut cover = vec![0u32; w * h];
    let mut peak = 0u32;
    let mut plot = |x: isize, y: isize, peak: &mut u32| {
        if x < 0 || y < 0 || x >= w as isize || y >= h as isize {
            return;
        }
        let c = &mut cover[y as usize * w + x as usize];
        *c += 1;
        *peak = (*peak).max(*c);
    };
    for &i in keep {
        let Some(&(a, b)) = segments.get(i as usize) else { continue };
        let (ax, ay) = (a.x - viewport.min.x, a.y - viewport.min.y);
        let (bx, by) = (b.x - viewport.min.x, b.y - viewport.min.y);
        if !(ax.is_finite() && ay.is_finite() && bx.is_finite() && by.is_finite()) {
            continue;
        }
        let steps = ((bx - ax).abs().max((by - ay).abs()).ceil() as usize).clamp(1, 4096);
        for s in 0..=steps {
            let t = s as f32 / steps as f32;
            plot((ax + (bx - ax) * t) as isize, (ay + (by - ay) * t) as isize, &mut peak);
        }
    }
    let lit = cover.iter().filter(|&&c| c > 0).count();
    let sat = cover.iter().filter(|&&c| c >= saturate).count();
    (lit, peak, sat)
}

// ─────────────────────────────────────────────────────────────────────────────
// 4. The per-frame PLAN — the one place a graph pane asks "what do I draw?"
// ─────────────────────────────────────────────────────────────────────────────

/// Everything a pane knows about the frame it is about to paint, already projected to
/// screen px. Index-aligned slices rather than a trait, so a pane with a completely
/// different node type (egui `Color32` chips, `vello` colours, map pins) fills them in
/// without adopting anyone else's model.
///
/// A short slice is treated as "all default": pass `&[]` for `label_priority` and every
/// label ranks equal, `&[]` for `edge_always` and no edge is protected.
pub struct FrameInput<'a> {
    /// Node centres in screen px.
    pub centres: &'a [Pos2],
    /// Measured label box per node, in px. An entry of `Vec2::ZERO` (or a short slice)
    /// means "this node has no label" and it is not offered to the placer.
    pub label_size: &'a [Vec2],
    /// Ranking for contested pixels. Higher wins.
    pub label_priority: &'a [f32],
    /// Labels that must never be dropped (selection / hover / search hit).
    pub label_pinned: &'a [bool],
    /// Edges as `(from, to)` node indices.
    pub edges: &'a [(u32, u32)],
    /// Edges that must never be thinned (the lit trace, a highlighted cycle).
    pub edge_always: &'a [bool],
    /// Ranking inside a saturated cell. Higher survives.
    pub edge_weight: &'a [f32],
    /// The pane rect in screen px. Everything outside it is rejected before any work,
    /// which is what makes the frame cost track the screen and not the dataset.
    pub viewport: Rect,
}

/// Which legibility cures to apply this frame. All-off is the historical painter.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct FrameOpts {
    pub thin_labels: bool,
    pub thin_edges: bool,
    pub label_pad: f32,
    pub edge_cell: f32,
    pub keep_per_bucket: usize,
}

impl Default for FrameOpts {
    fn default() -> Self {
        Self { thin_labels: false, thin_edges: false, label_pad: 2.0, edge_cell: 24.0, keep_per_bucket: 3 }
    }
}

impl FrameOpts {
    /// Both cures on, default tuning.
    #[must_use]
    pub fn legible() -> Self {
        Self { thin_labels: true, thin_edges: true, ..Self::default() }
    }

    /// Nothing enabled?
    #[must_use]
    pub fn is_off(&self) -> bool {
        !self.thin_labels && !self.thin_edges
    }
}

/// The plan: exactly which edges to stroke and exactly where each surviving label goes.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct FramePlan {
    /// Edge indices to draw, ascending. `None` = thinning off, draw them all.
    pub edges: Option<Vec<u32>>,
    /// Label placements. `None` = thinning off, paint them all as before.
    pub labels: Option<LabelPlacement>,
    pub report: FrameReport,
}

/// The observable summary of one frame's legibility work — what a `state_json` /
/// testmatrix row asserts on.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct FrameReport {
    pub labels_placed: usize,
    pub labels_suppressed: usize,
    pub labels_considered: usize,
    pub edges_drawn: usize,
    pub edges_thinned: usize,
    pub edges_considered: usize,
    pub edge_peak_before: usize,
    pub edge_peak_after: usize,
}

impl FrameReport {
    /// `state_json` fragment.
    #[must_use]
    pub fn state_json(&self) -> serde_json::Value {
        serde_json::json!({
            "labels_placed": self.labels_placed,
            "labels_suppressed": self.labels_suppressed,
            "labels_considered": self.labels_considered,
            "edges_drawn": self.edges_drawn,
            "edges_thinned": self.edges_thinned,
            "edges_considered": self.edges_considered,
            "edge_peak_before": self.edge_peak_before,
            "edge_peak_after": self.edge_peak_after,
        })
    }
}

/// **Plan one frame.** The single entry point every graph/map pane calls to decide what
/// is legible enough to draw. Pure: no `Ui`, no painter, no GPU — so the whole decision
/// is unit-testable and benchable without a window, and two panes cannot drift into
/// two different definitions of "readable".
#[must_use]
pub fn plan_frame(input: &FrameInput<'_>, opts: FrameOpts) -> FramePlan {
    let mut plan = FramePlan::default();

    if opts.thin_edges {
        let segs: Vec<(Pos2, Pos2)> = input
            .edges
            .iter()
            .map(|&(a, b)| {
                match (input.centres.get(a as usize), input.centres.get(b as usize)) {
                    (Some(&pa), Some(&pb)) => (pa, pb),
                    // A dangling endpoint draws nothing anyway; park it off-screen so
                    // index alignment with the caller's edge list survives.
                    _ => (Pos2::new(f32::NAN, f32::NAN), Pos2::new(f32::NAN, f32::NAN)),
                }
            })
            .collect();
        let res = thin_edges(
            &segs,
            input.edge_weight,
            input.edge_always,
            input.viewport,
            EdgeThinOpts { cell: opts.edge_cell, keep_per_bucket: opts.keep_per_bucket },
        );
        plan.report.edges_drawn = res.keep.len();
        plan.report.edges_thinned = res.dropped;
        plan.report.edges_considered = res.considered;
        plan.report.edge_peak_before = res.peak_density_before;
        plan.report.edge_peak_after = res.peak_density;
        plan.edges = Some(res.keep);
    } else {
        plan.report.edges_drawn = input.edges.len();
        plan.report.edges_considered = input.edges.len();
    }

    if opts.thin_labels {
        let cands: Vec<LabelCandidate> = input
            .centres
            .iter()
            .enumerate()
            .map(|(i, &c)| {
                let size = input.label_size.get(i).copied().unwrap_or(Vec2::ZERO);
                LabelCandidate {
                    // A zero-size label is parked far off-viewport (FINITE, so it reads
                    // as "not on screen" rather than as a malformed candidate): it is
                    // never considered and never counted as suppressed.
                    anchor: if size.x > 0.0 && size.y > 0.0 {
                        c
                    } else {
                        Pos2::new(f32::MAX * 0.5, f32::MAX * 0.5)
                    },
                    size,
                    priority: input.label_priority.get(i).copied().unwrap_or(0.0),
                    pinned: input.label_pinned.get(i).copied().unwrap_or(false),
                }
            })
            .collect();
        // Budget the placement at 8x what the viewport could physically hold. Past
        // that every candidate is a certain rejection, and candidates are in priority
        // order, so the tail that gets dropped is the tail nobody would have read.
        let (mut lw, mut lh) = (f32::MAX, f32::MAX);
        for sz in input.label_size.iter().filter(|s| s.x > 0.0 && s.y > 0.0) {
            lw = lw.min(sz.x);
            lh = lh.min(sz.y);
        }
        let capacity = if lw.is_finite() && lh.is_finite() && lw > 0.0 && lh > 0.0 {
            ((input.viewport.width() / lw) * (input.viewport.height() / lh)).ceil() as usize
        } else {
            0
        };
        let p = place_labels(
            &cands,
            input.viewport,
            PlaceOpts {
                pad: opts.label_pad,
                variable: true,
                clip_to_viewport: false,
                max_considered: capacity.saturating_mul(8).max(2048),
                // The graph frame planner has its own capacity model (`capacity`
                // above); the areal budget is the MAP's answer to the same question
                // and is set by that caller, so it stays off here.
                max_placed: 0,
            },
        );
        plan.report.labels_placed = p.placed.len();
        plan.report.labels_suppressed = p.suppressed;
        plan.report.labels_considered = p.considered;
        plan.labels = Some(p);
    }

    plan
}

#[cfg(test)]
mod tests {
    use super::*;
    use egui::{pos2, vec2};

    fn lattice(n: usize, span: f32) -> Vec<Pos2> {
        let side = (n as f32).sqrt().ceil() as usize;
        (0..n)
            .map(|i| {
                let (r, c) = (i / side, i % side);
                pos2(c as f32 / side as f32 * span, r as f32 / side as f32 * span)
            })
            .collect()
    }

    // ── ScreenGrid ───────────────────────────────────────────────────────────

    #[test]
    fn empty_and_degenerate_inputs_are_lossless_not_panics() {
        let g = ScreenGrid::build(&[]);
        assert!(g.is_empty());
        assert_eq!(g.nearest(&[], pos2(0.0, 0.0), 10.0), None);
        // Every point identical → one finite bin, and the probe still resolves.
        let pts = vec![pos2(5.0, 5.0); 100];
        let g = ScreenGrid::build(&pts);
        let hit = g.nearest(&pts, pos2(5.0, 5.0), 1.0).expect("degenerate extent still answers");
        assert_eq!(hit.index, 0, "ties resolve to the lowest index");
        // Non-finite points are indexed nowhere and can never be returned.
        let pts = vec![pos2(f32::NAN, 0.0), pos2(3.0, 3.0)];
        let g = ScreenGrid::build(&pts);
        assert_eq!(g.nearest(&pts, pos2(3.0, 3.0), 1.0).map(|h| h.index), Some(1));
    }

    /// The nearest-point answer must be the SAME as a brute-force linear scan, at
    /// every size and probe. If it were not, the index would be a fast wrong answer.
    #[test]
    fn nearest_agrees_with_brute_force_everywhere() {
        for n in [1usize, 7, 500, 5000] {
            let pts = lattice(n, 900.0);
            let g = ScreenGrid::build(&pts);
            for k in 0..40 {
                let probe = pos2((k * 37 % 900) as f32 + 0.5, (k * 53 % 900) as f32 + 0.5);
                let max_d = 200.0;
                let brute = pts
                    .iter()
                    .enumerate()
                    .map(|(i, p)| (i as u32, probe.distance(*p)))
                    .filter(|&(_, d)| d <= max_d)
                    .min_by(|a, b| a.1.total_cmp(&b.1).then(a.0.cmp(&b.0)));
                let got = g.nearest(&pts, probe, max_d);
                match (brute, got) {
                    (None, None) => {}
                    (Some((bi, bd)), Some(h)) => {
                        assert!(
                            (h.dist - bd).abs() < 1e-4,
                            "n={n} probe={probe:?}: grid {} vs brute {bd}",
                            h.dist
                        );
                        assert_eq!(h.index, bi, "n={n}: same winner as the linear scan");
                    }
                    (b, g2) => panic!("n={n} probe={probe:?}: brute={b:?} grid={g2:?}"),
                }
            }
        }
    }

    /// **THE claim, as data.** A hover probe must cost what is under the cursor, not
    /// what is in the dataset. `candidates` is the points actually distance-tested;
    /// a linear scan reports `n`. This is the assertion `facett-geomap`'s `PointGrid`
    /// did not have, which is why its lattice could span the world for months.
    #[test]
    fn hover_cost_tracks_the_neighbourhood_not_the_dataset() {
        let mut seen: Vec<(usize, usize)> = Vec::new();
        for n in [1000usize, 10_000, 100_000, 1_000_000] {
            let pts = lattice(n, 4000.0);
            let g = ScreenGrid::build(&pts);
            let hit = g.nearest(&pts, pos2(2000.0, 2000.0), 12.0).expect("a hit near the middle");
            // ABSOLUTE bound: one hover probe touches a neighbourhood, full stop.
            assert!(
                hit.candidates <= 128,
                "n={n}: examined {} points for one hover probe",
                hit.candidates
            );
            // The lattice spans the DATA, so occupancy stays near the target however
            // large or small the extent is — the bug `PointGrid` had.
            assert!(
                g.max_occupancy() <= 64,
                "n={n}: fullest bin holds {} (lattice mis-sized over the extent)",
                g.max_occupancy()
            );
            seen.push((n, hit.candidates));
        }
        // THE claim: the cost does not follow the dataset. n grows 1000×; a linear
        // scan's candidate count would grow 1000× with it.
        let (n0, c0) = seen[0];
        let (n1, c1) = *seen.last().unwrap();
        assert!(
            c1 <= c0 * 2,
            "dataset {n0} -> {n1} (×{}) but probe cost {c0} -> {c1}",
            n1 / n0
        );
    }

    #[test]
    fn query_rect_is_a_superset_of_the_true_contents_and_sorted() {
        let pts = lattice(2000, 800.0);
        let g = ScreenGrid::build(&pts);
        let r = Rect::from_min_max(pos2(100.0, 100.0), pos2(180.0, 180.0));
        let mut out = Vec::new();
        g.query_rect(r, &mut out);
        assert!(out.windows(2).all(|w| w[0] <= w[1]), "ascending index order");
        for (i, p) in pts.iter().enumerate() {
            if r.contains(*p) {
                assert!(out.contains(&(i as u32)), "point {i} inside the rect must be returned");
            }
        }
        assert!(out.len() < pts.len() / 4, "a small rect returns a small slice, got {}", out.len());
        // A rect entirely off the lattice costs nothing.
        let mut off = Vec::new();
        assert_eq!(g.query_rect(Rect::from_min_max(pos2(-9e3, -9e3), pos2(-8e3, -8e3)), &mut off), 0);
    }

    // ── labels ───────────────────────────────────────────────────────────────

    fn viewport() -> Rect {
        Rect::from_min_size(pos2(0.0, 0.0), vec2(800.0, 600.0))
    }

    /// **THE pixel oracle.** Rasterize the placed boxes: no pixel may be covered
    /// twice. The same candidates placed *without* collision avoidance pile up — so
    /// the assertion has a demonstrated failure mode, in-test, rather than a promise.
    #[test]
    fn placed_labels_never_share_a_pixel_and_the_unthinned_control_does() {
        // 400 labels crammed into a 200×150 patch — a guaranteed pile.
        let cands: Vec<LabelCandidate> = (0..400)
            .map(|i| {
                let x = 100.0 + ((i * 17) % 200) as f32;
                let y = 100.0 + ((i * 29) % 150) as f32;
                LabelCandidate::new(pos2(x, y), vec2(46.0, 12.0), (400 - i) as f32)
            })
            .collect();

        let out = place_labels(&cands, viewport(), PlaceOpts::default());
        let placed: Vec<Rect> = out.placed.iter().map(|p| p.rect).collect();
        assert_eq!(
            max_label_overlap(&placed, viewport(), 1.0),
            1,
            "collision avoidance: no pixel carries two labels"
        );
        assert!(out.suppressed > 0, "a real pile must actually suppress losers");
        assert!(!out.placed.is_empty(), "and must still draw the winners");

        // NEGATIVE CONTROL — the pre-fix behaviour: paint every candidate at its
        // anchor. The identical oracle reports a deep pile, so a placer that silently
        // degraded to "place everything" cannot pass the assertion above.
        let unthinned: Vec<Rect> = cands
            .iter()
            .map(|c| Rect::from_center_size(c.anchor, c.size))
            .collect();
        let control = max_label_overlap(&unthinned, viewport(), 1.0);
        assert!(control >= 5, "the control must overplot badly, got peak {control}");
    }

    /// Priority is honoured: with a hard collision, the higher-priority label wins the
    /// pixels. A placer that ignored priority would drop the important label.
    #[test]
    fn higher_priority_wins_a_contested_pixel() {
        let cands = vec![
            LabelCandidate::new(pos2(400.0, 300.0), vec2(60.0, 14.0), 1.0),
            LabelCandidate::new(pos2(402.0, 301.0), vec2(60.0, 14.0), 9.0),
        ];
        let opts = PlaceOpts { variable: false, ..PlaceOpts::default() };
        let out = place_labels(&cands, viewport(), opts);
        assert_eq!(out.placed.len(), 1);
        assert_eq!(out.placed[0].index, 1, "the priority-9 label is the one drawn");
        assert_eq!(out.suppressed, 1);
    }

    /// A pinned label (selection / hover / search hit) is NEVER suppressed, even when
    /// it collides — it outranks priority entirely, and two pinned labels both draw
    /// rather than one silently vanishing.
    #[test]
    fn pinned_labels_are_never_suppressed() {
        let opts = PlaceOpts { variable: false, ..PlaceOpts::default() };
        // A pinned label beats a much higher-priority ordinary one at the same pixels.
        let cands = vec![
            LabelCandidate::new(pos2(400.0, 300.0), vec2(60.0, 14.0), 100.0),
            LabelCandidate::new(pos2(401.0, 300.0), vec2(60.0, 14.0), 0.0).pinned(true),
        ];
        let out = place_labels(&cands, viewport(), opts);
        assert_eq!(out.placed.len(), 1);
        assert_eq!(out.placed[0].index, 1, "the pinned label is the one drawn");
        assert_eq!(out.suppressed, 1, "the ordinary label lost, as it must");

        // Two pinned labels on the same pixels: BOTH draw. The user asked for exactly
        // these two, so suppressing either is the wrong answer.
        let both = vec![
            LabelCandidate::new(pos2(400.0, 300.0), vec2(60.0, 14.0), 0.0).pinned(true),
            LabelCandidate::new(pos2(401.0, 300.0), vec2(60.0, 14.0), 0.0).pinned(true),
        ];
        let out = place_labels(&both, viewport(), opts);
        assert_eq!(out.placed.len(), 2, "pinned labels are never dropped");
        assert_eq!(out.suppressed, 0);
    }

    /// Variable placement really buys coverage: the same crowd places strictly more
    /// labels when alternates are allowed. Otherwise the ladder is dead code.
    #[test]
    fn variable_placement_places_more_than_one_shot() {
        let cands: Vec<LabelCandidate> = (0..120)
            .map(|i| {
                let x = 100.0 + ((i * 23) % 300) as f32;
                let y = 100.0 + ((i * 31) % 200) as f32;
                LabelCandidate::new(pos2(x, y), vec2(40.0, 12.0), i as f32)
            })
            .collect();
        let one = place_labels(&cands, viewport(), PlaceOpts { variable: false, ..Default::default() });
        let var = place_labels(&cands, viewport(), PlaceOpts { variable: true, ..Default::default() });
        assert!(
            var.placed.len() > one.placed.len(),
            "variable placement {} vs one-shot {}",
            var.placed.len(),
            one.placed.len()
        );
        let rects: Vec<Rect> = var.placed.iter().map(|p| p.rect).collect();
        assert_eq!(max_label_overlap(&rects, viewport(), 1.0), 1, "and still collision-free");
    }

    /// Off-viewport labels are never considered — the "cost tracks the screen" claim,
    /// as data. 100 000 candidates, 20 on screen ⇒ `considered` is 20.
    #[test]
    fn offscreen_labels_cost_nothing() {
        let mut cands: Vec<LabelCandidate> = (0..20)
            .map(|i| LabelCandidate::new(pos2(20.0 + i as f32 * 35.0, 300.0), vec2(24.0, 12.0), 1.0))
            .collect();
        cands.extend((0..100_000).map(|i| {
            LabelCandidate::new(pos2(50_000.0 + i as f32, -40_000.0), vec2(24.0, 12.0), 1.0)
        }));
        let out = place_labels(&cands, viewport(), PlaceOpts::default());
        assert_eq!(out.considered, 20, "only the on-screen candidates were considered");
        assert_eq!(out.suppressed, 0);
        assert!(
            out.collision_tests < 400,
            "bin-local tests, not quadratic: {} tests",
            out.collision_tests
        );
    }

    /// Determinism (FC-7): 64 repeats are byte-identical.
    #[test]
    fn label_placement_is_deterministic() {
        let cands: Vec<LabelCandidate> = (0..300)
            .map(|i| {
                LabelCandidate::new(
                    pos2(((i * 41) % 700) as f32, ((i * 67) % 500) as f32),
                    vec2(38.0, 12.0),
                    // Deliberate priority ties, so only the index tiebreak saves it.
                    (i % 5) as f32,
                )
            })
            .collect();
        let first = place_labels(&cands, viewport(), PlaceOpts::default());
        for _ in 0..64 {
            assert_eq!(place_labels(&cands, viewport(), PlaceOpts::default()), first);
        }
    }

    // ── edge thinning ────────────────────────────────────────────────────────

    fn hairball(n: usize) -> Vec<(Pos2, Pos2)> {
        let mut s = 0x2545_F491_4F6C_DD1Du64;
        let mut next = move || {
            s ^= s << 13;
            s ^= s >> 7;
            s ^= s << 17;
            (s >> 11) as f32 / (1u64 << 53) as f32
        };
        (0..n)
            .map(|_| {
                (
                    pos2(next() * 800.0, next() * 600.0),
                    pos2(next() * 800.0, next() * 600.0),
                )
            })
            .collect()
    }

    /// **THE pixel oracle for edges.** A 20 000-edge hairball saturates the pane; after
    /// thinning the saturated-pixel count collapses. Both numbers come from
    /// rasterizing the actual segments, and the unthinned control is measured in the
    /// same test — so "the hairball is readable now" is a comparison, not a claim.
    #[test]
    fn thinning_collapses_saturated_ink_and_the_control_proves_it_was_saturated() {
        let segs = hairball(20_000);
        let vp = viewport();
        let all: Vec<u32> = (0..segs.len() as u32).collect();
        let (lit_before, peak_before, sat_before) = edge_ink_profile(&segs, &all, vp, 4);

        let out = thin_edges(&segs, &[], &[], vp, EdgeThinOpts::default());
        let (lit_after, peak_after, sat_after) = edge_ink_profile(&segs, &out.keep, vp, 4);

        assert!(sat_before > 10_000, "the control hairball must really be saturated: {sat_before}");
        assert!(
            sat_after * 4 < sat_before,
            "thinning must cut saturated pixels hard: {sat_before} -> {sat_after}"
        );
        assert!(peak_after < peak_before, "peak pile {peak_before} -> {peak_after}");
        assert!(lit_after > 0 && lit_after < lit_before, "still draws a graph: {lit_before} -> {lit_after}");
        // The counters agree with the pixels.
        assert!(out.peak_density < out.peak_density_before);
        assert_eq!(out.keep.len() + out.dropped, out.considered);
    }

    /// A SPARSE region is not touched. Random subsampling would thin it anyway; this
    /// is the property that makes density-aware thinning worth the code.
    #[test]
    fn a_sparse_graph_loses_no_edges() {
        let segs: Vec<(Pos2, Pos2)> = (0..12)
            .map(|i| {
                let y = 40.0 + i as f32 * 45.0;
                (pos2(30.0, y), pos2(760.0, y + 6.0))
            })
            .collect();
        let out = thin_edges(&segs, &[], &[], viewport(), EdgeThinOpts::default());
        assert_eq!(out.dropped, 0, "nothing to thin in a sparse graph");
        assert_eq!(out.keep.len(), segs.len());
    }

    /// Flagged edges (path / cycle / hover) survive the densest bucket.
    #[test]
    fn always_keep_edges_survive_any_density() {
        let segs = hairball(5000);
        let mut always = vec![false; segs.len()];
        for i in (0..segs.len()).step_by(500) {
            always[i] = true;
        }
        let out = thin_edges(&segs, &[], &always, viewport(), EdgeThinOpts { cell: 24.0, keep_per_bucket: 0 });
        for (i, &f) in always.iter().enumerate() {
            if f {
                assert!(out.keep.contains(&(i as u32)), "flagged edge {i} was thinned away");
            }
        }
        assert_eq!(out.keep.len(), always.iter().filter(|&&f| f).count(), "quota 0 keeps only the flagged");
    }

    /// Weight ranks the survivors — the heaviest edge in a bucket is the one kept.
    #[test]
    fn the_heaviest_edge_in_a_bucket_is_the_survivor() {
        // Four parallel, near-identical segments in one bin + direction bucket.
        let segs: Vec<(Pos2, Pos2)> = (0..4)
            .map(|i| (pos2(100.0, 100.0 + i as f32), pos2(140.0, 100.0 + i as f32)))
            .collect();
        let weight = vec![0.1, 0.2, 9.0, 0.3];
        let out = thin_edges(&segs, &weight, &[], viewport(), EdgeThinOpts { cell: 24.0, keep_per_bucket: 1 });
        assert_eq!(out.keep, vec![2], "the weight-9 edge is the one drawn");
    }

    /// Determinism (FC-7): the survivors are a pure function of the input, not of
    /// `HashMap` bucket order. 64 repeats.
    #[test]
    fn edge_thinning_is_deterministic() {
        let segs = hairball(4000);
        let weight: Vec<f32> = (0..segs.len()).map(|i| (i % 7) as f32).collect();
        let first = thin_edges(&segs, &weight, &[], viewport(), EdgeThinOpts::default());
        for _ in 0..64 {
            assert_eq!(thin_edges(&segs, &weight, &[], viewport(), EdgeThinOpts::default()), first);
        }
        assert!(first.keep.windows(2).all(|w| w[0] < w[1]), "ascending, so paint order is preserved");
    }

    /// Off-viewport edges are rejected before any work.
    #[test]
    fn offscreen_edges_cost_nothing() {
        let mut segs = hairball(50);
        segs.extend((0..50_000).map(|i| {
            (pos2(-90_000.0 - i as f32, -90_000.0), pos2(-89_000.0 - i as f32, -89_000.0))
        }));
        let out = thin_edges(&segs, &[], &[], viewport(), EdgeThinOpts::default());
        assert_eq!(out.considered, 50, "only on-screen edges were considered");
    }
}