facett-core 0.1.17

//! **Picking, built ONCE.** The census found three hand-rolled pickers on the
//! map side (`facett-map::hit_test_way`, `facett-geomap`'s pin hit-test,
//! `facett-geomap`'s hotspot select), two more on the graph side
//! (`facett-graphview::PickIndex`, `facett-graphnav::HoverIndex`), **none** in
//! `facett-map3d`, and no primitive at all in `facett-core`. Drill-down is
//! useless without a click, so this is the one.
//!
//! ## Two lanes, one id space
//! * **CPU lane** — a [`ScreenGrid`](crate::legibility::ScreenGrid) over the
//!   projected anchors. Exact, deterministic, headless-testable, no GPU.
//! * **GPU lane** — the same [`PickId`] written as a colour into an offscreen
//!   `R32Uint` target; a click reads one texel back. This is deck.gl's one
//!   remaining lead, and it is the *same 32-bit id* the CPU lane returns, so a
//!   test can assert the two lanes agree. (Pass 1 defines the id encoding and
//!   the CPU lane; the offscreen target is the shader pass.)
//!
//! ## The id encoding
//! `PickId` is `layer << 24 | feature`, so one buffer serves every layer in the
//! frame — which is what use case 7 (a graph drawn on geography) requires: one
//! click, two position sources, one answer. `0` is reserved for **nothing**, so
//! a cleared target reads as a miss.

use crate::legibility::ScreenGrid;
use egui::{Pos2, Rect, Vec2};

/// **What shape a feature occupies for the purpose of a click.**
///
/// The census found the same click implemented eight times across the graph
/// crates and three more across the map crates, differing only in this enum. A
/// map pin is a radius; a graph chip is a box; a road is a nearest-point. Naming
/// the difference is what lets one index serve them all — and it is load-bearing,
/// not cosmetic: when chips overlap (they do at low zoom, `BOX_W` is 184 px)
/// "nearest centre" and "first box that contains the point" are **different
/// nodes**, so a picker that silently swaps one for the other is wrong in a way
/// no smoke test notices.
#[derive(Clone, Copy, Debug, PartialEq)]
pub enum PickShape {
    /// A disc of `r` screen px around the anchor. Nearest wins.
    Radius(f32),
    /// An axis-aligned box of `half`-extent screen px around the anchor. The
    /// **lowest feature index** that contains the probe wins — paint order.
    Box(Vec2),
}

impl Default for PickShape {
    fn default() -> Self {
        Self::Radius(8.0)
    }
}

/// Layer slot in a frame. 8 bits — 255 simultaneous layers, `0` reserved.
pub type LayerId = u8;

/// A 32-bit pick identity: `layer << 24 | feature`. `PickId(0)` = nothing.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct PickId(pub u32);

/// Features are 24-bit inside a pick id. A layer with more than this many
/// features must be split — asserted, never silently truncated.
pub const MAX_FEATURE: u32 = (1 << 24) - 1;

impl PickId {
    /// Encode. `layer` must be `1..=255` and `feature` `<= MAX_FEATURE`;
    /// out-of-range inputs encode as [`PickId::NOTHING`] rather than aliasing
    /// onto another feature (a silent alias is a wrong click, forever).
    #[must_use]
    pub fn new(layer: LayerId, feature: u32) -> Self {
        if layer == 0 || feature > MAX_FEATURE {
            return Self::NOTHING;
        }
        Self(((layer as u32) << 24) | feature)
    }

    /// The reserved "no feature here" id. A cleared GPU target reads as this.
    pub const NOTHING: PickId = PickId(0);

    #[must_use]
    pub fn is_nothing(self) -> bool {
        self.0 == 0
    }
    #[must_use]
    pub fn layer(self) -> LayerId {
        (self.0 >> 24) as u8
    }
    #[must_use]
    pub fn feature(self) -> u32 {
        self.0 & MAX_FEATURE
    }

    /// The id as the RGBA bytes a colour-encoded GPU target would carry
    /// (little-endian, so `R` is the low feature byte). The shader half writes
    /// the `u32` directly; this exists so an 8-bit-per-channel readback path and
    /// the CPU lane provably agree on the same number.
    #[must_use]
    pub fn to_rgba(self) -> [u8; 4] {
        self.0.to_le_bytes()
    }
    #[must_use]
    pub fn from_rgba(b: [u8; 4]) -> Self {
        Self(u32::from_le_bytes(b))
    }
}

/// What a pick found, **and how much work it did** — the anti-lie field, same
/// discipline as [`NearestHit`](crate::legibility::NearestHit).
#[derive(Clone, Copy, Debug, Default, PartialEq)]
pub struct PickHit {
    pub id: PickId,
    /// Screen-space distance in px from the probe to the anchor.
    pub dist: f32,
    /// Anchors actually distance-tested. A linear scan reports the whole layer.
    pub candidates: usize,
}

/// The CPU pick index: one [`ScreenGrid`] per layer over that layer's projected
/// anchors, plus the id map. Rebuilt when the camera or any source's
/// [`generation`](super::source::PositionSource::generation) changes.
#[derive(Debug, Default)]
pub struct PickIndex {
    layers: Vec<PickLayer>,
    /// The cache key the index was built for (camera epoch ⊕ source generations).
    key: u64,
}

#[derive(Debug)]
struct PickLayer {
    layer: LayerId,
    grid: ScreenGrid,
    /// The projected anchors the grid indexes (`ScreenGrid` bins indices, not
    /// points, so the points travel alongside it).
    anchors: Vec<Pos2>,
    /// `grid` point index -> caller feature id.
    features: Vec<u32>,
    /// What a feature of this layer occupies on screen.
    shape: PickShape,
}

impl PickIndex {
    /// The key this index was built against — compare before reusing.
    #[must_use]
    pub fn key(&self) -> u64 {
        self.key
    }

    /// True when the index is already valid for `key` (nothing to rebuild).
    #[must_use]
    pub fn is_current(&self, key: u64) -> bool {
        !self.layers.is_empty() && self.key == key
    }

    /// Drop everything and start a new frame's index under `key`.
    pub fn begin(&mut self, key: u64) {
        self.layers.clear();
        self.key = key;
    }

    /// Add one layer's projected anchors. `features[i]` is the caller feature id
    /// of `anchors[i]`.
    pub fn push_layer(&mut self, layer: LayerId, anchors: &[Pos2], features: Vec<u32>, shape: PickShape) {
        debug_assert_eq!(anchors.len(), features.len(), "anchors and features must be index-aligned");
        self.layers.push(PickLayer {
            layer,
            grid: ScreenGrid::build(anchors),
            anchors: anchors.to_vec(),
            features,
            shape,
        });
    }

    /// **The click.** Each layer answers by its own [`PickShape`]; the latest
    /// layer wins a tie — so an overlay drawn on top of a map also picks on top
    /// of it, which is exactly what use case 7 needs.
    #[must_use]
    pub fn pick(&self, probe: Pos2) -> PickHit {
        let mut best = PickHit::default();
        let mut found = false;
        for l in &self.layers {
            let hit = match l.shape {
                PickShape::Radius(r) => l.grid.nearest(&l.anchors, probe, r.max(1.0)).map(|h| {
                    best.candidates += h.candidates;
                    (h.index, h.dist)
                }),
                PickShape::Box(half) => {
                    // The chip test, index-backed: every possible winner has its
                    // anchor inside `probe ± half`, so one rect query returns a
                    // superset, the exact componentwise test filters it, and the
                    // LOWEST index wins — the paint-order answer a linear
                    // `find_map` over the feature list returns.
                    let mut cands: Vec<u32> = Vec::new();
                    l.grid.query_rect(Rect::from_center_size(probe, half * 2.0), &mut cands);
                    best.candidates += cands.len();
                    cands.sort_unstable();
                    cands
                        .into_iter()
                        .find(|&i| {
                            let c = l.anchors[i as usize];
                            (probe.x - c.x).abs() <= half.x && (probe.y - c.y).abs() <= half.y
                        })
                        .map(|i| (i, (l.anchors[i as usize] - probe).length()))
                }
            };
            let Some((index, dist)) = hit else { continue };
            if !found || dist <= best.dist {
                found = true;
                let feat = l.features.get(index as usize).copied().unwrap_or(u32::MAX);
                best.id = PickId::new(l.layer, feat);
                best.dist = dist;
            }
        }
        best
    }

    #[must_use]
    pub fn layer_count(&self) -> usize {
        self.layers.len()
    }
}

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

    #[test]
    fn id_round_trips_through_rgba_and_fields() {
        let id = PickId::new(3, 1_234_567);
        assert_eq!(id.layer(), 3);
        assert_eq!(id.feature(), 1_234_567);
        assert_eq!(PickId::from_rgba(id.to_rgba()), id);
        assert!(!id.is_nothing());
    }

    /// RED-PROVEN: remove the guard in `PickId::new` and this fails — feature
    /// `1<<24` would alias onto layer 1 feature 0.
    #[test]
    fn out_of_range_encodes_as_nothing_never_as_an_alias() {
        assert!(PickId::new(0, 5).is_nothing(), "layer 0 is reserved");
        assert!(PickId::new(1, MAX_FEATURE + 1).is_nothing(), "a 25-bit feature must not alias");
        assert_ne!(PickId::new(1, 0), PickId::NOTHING, "a real feature must not read as a miss");
    }

    #[test]
    fn pick_returns_the_nearest_anchor_and_reports_its_work() {
        let anchors: Vec<Pos2> = (0..1000).map(|i| Pos2::new((i % 50) as f32 * 10.0, (i / 50) as f32 * 10.0)).collect();
        let mut idx = PickIndex::default();
        idx.begin(1);
        idx.push_layer(1, &anchors, (0..1000).collect(), PickShape::Radius(8.0));

        let hit = idx.pick(Pos2::new(101.0, 60.0));
        assert_eq!(hit.id.layer(), 1);
        // (100, 60) is column 10, row 6 -> index 6*50 + 10 = 310.
        assert_eq!(hit.id.feature(), 310, "picked the wrong anchor");
        assert!(hit.dist <= 2.0);
        assert!(hit.candidates < 1000, "tested {} of 1000 — that is a linear scan", hit.candidates);
    }

    #[test]
    fn a_click_on_empty_space_is_nothing() {
        let anchors = vec![Pos2::new(0.0, 0.0)];
        let mut idx = PickIndex::default();
        idx.begin(1);
        idx.push_layer(1, &anchors, vec![7], PickShape::Radius(4.0));
        assert!(idx.pick(Pos2::new(500.0, 500.0)).id.is_nothing());
    }

    #[test]
    fn the_upper_layer_wins_a_contested_pixel() {
        let a = vec![Pos2::new(10.0, 10.0)];
        let mut idx = PickIndex::default();
        idx.begin(1);
        idx.push_layer(1, &a, vec![100], PickShape::Radius(12.0)); // the map
        idx.push_layer(2, &a, vec![200], PickShape::Radius(12.0)); // the graph on top of it
        let hit = idx.pick(Pos2::new(10.0, 10.0));
        assert_eq!((hit.id.layer(), hit.id.feature()), (2, 200));
    }

    /// RED-PROVEN: drop the `cands.sort_unstable()` (or switch `Box` to nearest)
    /// and this fails — overlapping chips make "nearest" a *different* node from
    /// "first in paint order", and the fast answer would silently be wrong.
    #[test]
    fn box_shape_matches_the_linear_scan_over_overlapping_chips() {
        // Chips 184x28 px on a 40 px pitch: they overlap heavily, like a graph
        // board at low zoom.
        let half = Vec2::new(92.0, 14.0);
        let anchors: Vec<Pos2> = (0..300).map(|i| Pos2::new((i % 20) as f32 * 40.0, (i / 20) as f32 * 18.0)).collect();
        let mut idx = PickIndex::default();
        idx.begin(1);
        idx.push_layer(1, &anchors, (0..300).collect(), PickShape::Box(half));

        let reference = |p: Pos2| -> Option<u32> {
            anchors.iter().position(|c| (p.x - c.x).abs() <= half.x && (p.y - c.y).abs() <= half.y).map(|i| i as u32)
        };
        let mut hits = 0;
        for gx in 0..30 {
            for gy in 0..20 {
                let p = Pos2::new(gx as f32 * 27.0 - 40.0, gy as f32 * 15.0 - 20.0);
                let got = idx.pick(p);
                let want = reference(p);
                match want {
                    Some(w) => {
                        assert_eq!(got.id.feature(), w, "probe {p:?}: index picked {:?}, scan picked {w}", got.id.feature());
                        hits += 1;
                    }
                    None => assert!(got.id.is_nothing(), "probe {p:?}: index invented a hit"),
                }
            }
        }
        assert!(hits > 100, "only {hits} probes landed on a chip — the sweep proves nothing");
    }
}